题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=6667
题目:
t≤25个样例,n≤1e6个班级,每个班级有个人,做了杯奶茶,每个人只能喝一杯奶茶且不能喝自己班做的奶茶。
问最多有多少学生能喝到奶茶?
input1:
1
2
3 4
2 1
output2:
3
input2:
1
4
4 2
3 5
3 4
2 1
output2:
12
解题思路:
按照从大到小排序,对于奶茶数目,按照贪心的思想,一定要先把数目最大的分配给其他人,那么分配给谁呢?做出的奶茶数目少的班级应该最后再安排哪些人喝他们的奶茶(当然可能最后没有人被分配到这些班级),这样才能使没被喝的奶茶数目最少。所以先把小的班级的人分配给大的班级去喝奶茶。
这样处理完之后需要考虑最后处理到的那个班级是否还有奶茶,因为那个班级的人不能和自己班的奶茶,对n=1这种情况特判。
ac代码:
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
typedef long long ll;
struct node{
int a, b;
friend bool operator < (node aa, node bb)
{
return aa.b > bb.b;
}
}c[maxn];
ll suma, sumb;
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
suma = sumb = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d %d", &c[i].a, &c[i].b);
suma += c[i].a;
sumb += c[i].b;
}
if(n == 1)
{
printf("0\n");
continue;
}
sort(c+1, c+1+n);
int pb = 1, pa = n;
ll ans = 0;
while(pb <=n && pa >= 1)
{
if(pb == pa)
{
pa--;
continue;
}
if(c[pa].a < c[pb].b)
{
int x = c[pa].a;
ans += x;
suma -= x; sumb -= x;
c[pb].b -= x;
c[pa].a = 0;
pa--;
}
else if(c[pa].a > c[pb].b)
{
int x = c[pb].b;
ans += x;
suma -= x; sumb -= x;
c[pb].b = 0;
c[pa].a -= x;
pb++;
}
else
{
int x = c[pb].b;
ans += x;
suma -= x; sumb -= x;
c[pb].b = 0;
c[pa].a = 0;
pb++;
pa--;
}
}
if(pa == 0) pa++;
if(pa >= 1 && c[pa].b != 0) ans += min(suma, sumb - c[pa].b);
else ans += min(suma, sumb);
printf("%lld\n", ans);
}
return 0;
}