HDOJ(HDU).1864 最大报销额

题意分析

题目有点问题，原题中说的

---

单项物品的价值不得超过600元

应该是单类物品的价值不能超过600元。

一开始以为是01背包，后来按贪心写过了。

一张一张发票处理，读入一整张发票的数据。然后检查一下里面是否有不能报销的类别（即除ABC）以外的其他类。然后看一下单类的价钱是否超过600。如都满足题目所说能够报销的要求，则把它存到b数组里面，接着对b数组按照金额降序排序，结合给的经费，先报销大的，再报销小的，遍历一遍即可。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 35

using 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;

}