HDU_5527_Too Rich

来源:http://www.cnblogs.com/edward108/archive/2017/10/08/7636318.html
-Advertisement-
Play Games

Too Rich Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1410 Accepted Submission(s): 362 Probl ...


Too Rich

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1410    Accepted Submission(s): 362


Problem Description You are a rich person, and you think your wallet is too heavy and full now. So you want to give me some money by buying a lovely pusheen sticker which costs pdollars from me. To make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.

For example, if p=17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.
 

 

Input The first line contains an integer T indicating the total number of test cases. Each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number ci means how many coins/banknotes in denominations of i dollars in your wallet.

1T20000
0p109
0ci100000
 

 

Output For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. If you cannot pay for exactly p dollars, please simply output '-1'.  

 

Sample Input 3 17 8 4 2 0 0 0 0 0 0 0 100 99 0 0 0 0 0 0 0 0 0 2015 9 8 7 6 5 4 3 2 1 0  

 

Sample Output 9 -1 36  

 

Source 2015ACM/ICPC亞洲區長春站-重現賽(感謝東北師大)  
  • 首先由於p的數值範圍的緣故排除用完全背包來解
  • 用dfs枚舉紙幣張數爆搜肯定會tle
  • 所以往貪心的思想考慮
  • 朴素的想法是對於p從小面額的湊到大面額的紙幣
  • 但是這道題中紙幣的面額如果以倍數為關係建圖可以發現(20,50)和(200,500)會分別從10和100的節點分叉,但是其他節點均可表示比當前節點大的所有面額的紙幣
  • 這個特性意味著用小面額20或200有湊不出50和500以及其奇數倍數值的情況
  • 反思之前提到的朴素的貪心想法
  • 如果湊到最後出現湊的數額不等於p
  • 則一定是最後加的當前最大面額導致的
  • 補救的辦法應是用之前使用的小面額紙幣湊當前導致超範圍的紙幣的面額
  • 那麼如之前所述
  • 10種紙幣的面額不是一種很好的結構
  • 不能保證小面額紙幣一定可以湊成任意大面額紙幣
  • 就存在不可補救的情況存在
  • 而且我們沒法保證當前湊數的結果是正確的湊數結果
  • 那有沒有補救的辦法呢?
  • 還是有滴呀
  • 只要把紙幣面額更改成最優結構即可
  • 就是每次使用兩張50或500,就把這種面額的紙幣算是取消了
  • 之後就剩下8種面額的紙幣,而且都滿足可以湊成任意比當前面額大的紙幣的條件
  • 剩下的就是討論50和500兩種紙幣使用張數奇偶性的問題了
  • 4種情況,在貪心前加上就行
  • 高中數學老師講得好啊!“正難則反”
  • 這個題就可以反向思維,只要湊出紙幣剩餘面額的最小張數,減一下就是結果啊!
  • 如果正向考慮,應該是貪心湊數,最後對於多出來的數值用小面額先代替大面額之後打補丁
  • 好吧,很麻煩
  • 但是反向來做,不用代替和打補丁,就是直接用最大面值來湊,不存在打補丁的問題

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int c[11]={0,1,5,10,20,50,100,200,500,1000,2000};
25 int a[20], b[20], T, ans, tot;
26 LL p, sum;
27 int main(){
28     // freopen("in.txt","r",stdin);
29     // freopen("out.txt","w",stdout);
30     while(~scanf("%d",&T)){
31         while(T--){
32             sum=0;
33             tot=0;
34             ans=inf;
35             scanf("%lld",&p);
36             for(int i=1;i<11;i++){
37                 scanf("%d",&a[i]);
38                 tot+=a[i];
39                 sum+=a[i]*c[i];
40             }
41             if(sum<p){
42                 printf("-1\n");
43                 continue;
44             }
45             p=sum-p;
46             memcpy(b,a,sizeof(a));
47             for(int i=0;i<2;i++)
48                 for(int j=0;j<2;j++)
49                     if(i<=a[5] && j<=a[8]){
50                         b[5]=a[5]-i;
51                         b[8]=a[8]-j;
52                         LL t=p-i*c[5]-j*c[8];
53                         int cnt=i+j;
54                         for(int k=10;k>0&&t>0;k--){
55                             int del=min(b[k],(int)t/c[k]);
56                             if((k==5||k==8)&&(del&1))
57                                 del--;
58                             t-=del*c[k];
59                             cnt+=del;
60                         }
61                         if(t==0)
62                             ans=min(ans,cnt);
63                     }
64             if(ans==inf)
65                 ans=-1;
66             else
67                 ans=tot-ans;
68             printf("%d\n",ans);
69         }
70     }
71     return 0;
72 }

 

 

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 這一節主要介紹List介面的幾個實現類的區別: 1.線程安全 Vector是線程安全的,而ArrayList和LinkedList是非線程安全的。從源碼中我們可知,Vector類中的方法大部分都是同步的,即被synchronized關鍵字修飾;而那些沒有被synchronized關鍵字修飾的方法都是 ...
  • Count a * b Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 872 Accepted Submission(s): 315 Pro ...
  • Travelling HDU - 3001 方法:3進位狀態壓縮dp(更好的方法是預處理出每個狀態數字對應的y數組,然後用刷表,時間複雜度可以少一個n) 曾經錯在: 1.65行,兩個min打成max 2.每一組數據沒有重置ans(浪費2小時) ...
  • java.io.File類用於表示文件(目錄) File類只用於表示文件(目錄)的信息(名稱、大小等),不能用於文件內容的訪問 RandomAccessFile java提供的對文件內容的訪問,既可以讀文件,也可以寫文件。 RandomAccessFile支持隨機訪問文件,可以訪問文件的任意位置 1 ...
  • 操作HTML標簽的時候,我們首先要找到HTML標簽的位置,然後進行操作,下麵來看看集中查找標簽的方法,如下: 1、Id選擇器 -- Id在HTML中是唯一的,通過Id進行查找,Id對應的是#號 id ==》# 上面HTML代碼,下麵使用$("#i10")進行查找,查找Id="i10"的標簽,如下: ...
  • 對於PHP開發者來說,一旦某個產品投入使用,應該立即將 display_errors選項關閉,以免因為這些錯誤所透露的路徑、資料庫連接、數據表等信息而遭到黑客攻擊。但是,任何一個產品在投入使用後,都難 免會有錯誤出現,那麼如何記錄一些對開發者有用的錯誤報告呢?我們可以在單獨的文本文件中將錯誤報告作為 ...
  • php有哪幾種錯誤提示 1.notice : 註意 2.waring : 警告 3.error : 錯誤 PHP中都有哪幾種查錯方法? 1、語法檢查--php配置文件里,把錯誤顯示選項都打開或者代碼開始部分,加error_reporting(E_ALL)2、邏輯檢查--設置斷點,在斷點前寫日誌 er ...
  • 大學畢業後筆者進入一家外企,做企業CRM系統開發,那時候開發效率最高的高級程式語言,毫無疑問是C#。恰逢公司也在擴張,招聘了不少.net程式員,筆者作為應屆生,也樂呵呵的加入到.net程式員行列中。 C#.net非常容易上手,之前在大學里,做過winform和webform開發,也曾經在老師那裡承接 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...