芜湖市2018市队选拔Day2T1

好激动啊，Day2竟然AK了！

Day2T1养宠物

Description
badgers是可爱的动物，Smart想拥有一些。宠物店提供N个badgers，编号为1..N，Smart都很喜欢，所以他想拥有得越多越好。初始，每个badger每天需要固定量的食物。但是，如果它看见别的badger也在吃东西，它会觉得饥饿而吃更多的东西。一个badger每多一个同食者需要增加一个固定量的食物。
h[i]表示第i个badger单独进食所需要的食物。g[i]表示第i个badger在每多一个同食者的情况下增加的食物量。Smart每天最多可以供应totalFood量的食物，那么他最多可以养多少只badgers。
注意：Smart是把badgers放在一起养，所以每一只badger都能看到其他badger吃东西。

Input
第一行两个整数N和totalFood。
第二行N个整数，第i个为h[i]。
第三行N个整数，第i个为g[i]。

Output
一个整数，表示Smart最多可以养多少只badgers。

Sample Input
#1
3 7
1 2 3
2 2 1

#2
4 19
5 2 1 5
0 2 4 1

Sample Output
#12

#2
3
Hint

30%的数据：N≤10；
100%的数据：1≤N≤50，1≤h[i]≤1000，0≤g[i]≤1000，1≤totalFood≤1000000。

【题解】
    这题首先想到的是暴力。
    打一张表出来，其中f[i][j]是第i个动物在和j个人供餐时的食量。

将数量从高到低枚举，按照当前数量i的饭量排升序之后选前i个。看看是否小于等于totalFood。如果是，输出并退出，否则继续枚举下一个时间。

【源代码】

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int S=;

 int n,m,s;

 struct info

 {

 int h,g;

 }a[S];

 bool cmp(info a,info b)

 {

     return a.h<b.h;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++)

     scanf("%d",&a[i].h);

     for (int i=;i<=n;i++)

     {

         scanf("%d",&a[i].g);

         a[i].h+=a[i].g*(n-);

     }

     for (int i=n;i;i--)

     {

         sort(a+,a++n,cmp);s=;

         for (int j=;j<=i;j++)

         s+=a[j].h;

         if (s<=m)

         {

             printf("%d",i);

             return ;

         }

         for (int j=;j<=n;j++)

         a[j].h-=a[j].g;

     }

     puts("");

     return ;

 }

（20180325）