HDOJ(HDU).1864 最大報銷額 (貪心)

2019-11-08 01:52:20

字體：大中小

來源：轉載

供稿：網友

HDOJ(HDU).1864 最大報銷額

題意分析

題目有點問題，原題中說的

單項物品的價值不得超過600元

應該是單類物品的價值不能超過600元。

一開始以為是01背包，后來按貪心寫過了。

一張一張發票處理，讀入一整張發票的數據。然后檢查一下里面是否有不能報銷的類別（即除ABC）以外的其他類。然后看一下單類的價錢是否超過600。如都滿足題目所說能夠報銷的要求，則把它存到b數組里面，接著對b數組按照金額降序排序，結合給的經費，先報銷大的，再報銷小的，遍歷一遍即可。

代碼總覽

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 35using namespace std;double b[nmax];double a[26];void check(int pos){ double sum = 0; bool can = true; for(int i = 0 ;i<=25;++i){ sum+=a[i]; if(i<3){ if(a[i]>600) can = false; }else if(i >=3){ if(a[i]!=0) can = false; } } if(can) b[pos] = sum;}bool cmp(double a ,double b){ return a>b;}int main(){ //freopen("in.txt","r",stdin); int n; double m; while(scanf("%lf %d",&m,&n) && n){ memset(b,0,sizeof(b)); for(int i = 1; i<=n; ++i){ int ca; scanf("%d",&ca); char c; double t; memset(a,0,sizeof(a)); for(int j = 1; j<=ca;++j){ scanf(" %c:%lf",&c,&t); a[c-'A']+=t; } check(i); } double t; sort(b+1,b+1+n,cmp); t = m; double cnt = 0; for(int i =1;i<=n;++i ){ if(b[i]<=t) {t-=b[i];cnt+=b[i];} }