hdu 6667 Roundgod and Milk Tea

左手的ㄟ右手 2023-10-11 09:37 23阅读 0赞

[题目][Link 1]

题意：

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

题解（贪心）：

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

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

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

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

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

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11353621.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6667
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif