hdu 6667 Roundgod and Milk Tea

题目

题意:

 t组输入,之后一个n代表有n个班级。之后的n行,第一个数代表每班有多少人,第二个代表这个班级能够产生多少杯奶茶,每人只能喝一杯奶茶且不能喝自己班级制作的,问最多能有多少人能喝到奶茶

 

题解(贪心):

先找出来奶茶总数和学生总数,他们中的最小值就是(最多能喝到奶茶的人数)

当总人数小于奶茶总数时:

那么就只需要一个班级一个班级的判断:除了自己班级制作的奶茶外,其他班级制作的奶茶能不能够本班级人喝,如果不够就让我们之前找出来的(最多能喝到奶茶的人数)减去多少人喝不到奶茶的人数

当总奶茶数少于人总数时:

还是一个一个班级的判断:自己班级制作的奶茶多不多于除了自己班级外其他班级的总人数,如果多于总人数,那么就证明一些奶茶只能剩余下来,又因为奶茶数本来就少与总人数,所以在原来(最多能喝到奶茶的人数)的基础上,要减去剩余下来的奶茶数

 

代码:

hdu 6667 Roundgod and Milk Tea
 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <string.h>
 5 using namespace std;
 6 const int maxn = 1e6+5;
 7 typedef long long ll;
 8 struct shudui
 9 {
10     ll a,b;
11 } m[maxn];
12 int main()
13 {
14     ll t;
15     scanf("%lld",&t);
16     while(t--)
17     {
18         ll n,sum1=0,sum2=0;
19         scanf("%lld",&n);
20         for(ll i=1; i<=n; ++i)
21         {
22             scanf("%lld%lld",&m[i].a,&m[i].b);
23             sum1+=m[i].a;
24             sum2+=m[i].b;
25         }
26         ll ans=0;
27         if(sum1<=sum2)
28         {
29             for(ll i=1; i<=n; ++i)
30             {
31                 if(m[i].a>sum2-m[i].b)
32                     ans=ans+m[i].a-sum2+m[i].b;
33             }
34             printf("%lld\n",sum1-ans);
35         }
36         else
37         {
38             for(ll i=1; i<=n; ++i)
39             {
40                 if(m[i].b>sum1-m[i].a)
41                     ans=ans+m[i].b-sum1+m[i].a;
42             }
43             printf("%lld\n",sum2-ans);
44         }
45     }
46     return 0;
47 }
View Code

 

上一篇:LeetCode 49. 字母异位词分组


下一篇:Roundgod and Milk Tea(多校8 ,1011 )贪心