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];} } PRintf("%.2f/n",cnt); } return 0;}

上一篇：js根据经纬度计算两点距离

下一篇：[Shell][find]用法