Roundgod and Milk Tea

时间 2020-05-08 标签 roundgod milk tea

Problem Description

Roundgod is a famous milk tea lover at Nanjing University second to none. This year, he plans to conduct a milk tea festival. There will be n classes participating in this festival, where the ith class has ai students and will make bi cups of milk tea.

Roundgod wants more students to savor milk tea, so he stipulates that every student can taste at most one cup of milk tea. Moreover, a student can't drink a cup of milk tea made by his class. The problem is, what is the maximum number of students who can drink milk tea?

Input

The first line of input consists of a single integer T (1≤T≤25), denoting the number of test cases.

Each test case starts with a line of a single integer n (1≤n≤106), the number of classes. For the next n lines, each containing two integers a,b (0≤a,b≤109), denoting the number of students of the class and the number of cups of milk tea made by this class, respectively.

It is guaranteed that the sum of n over all test cases does not exceed 6×106.

Output

For each test case, print the answer as a single integer in one line.

Sample Input

1 2 3 4 2 1

Sample Output

解题报告：这道题目一上来想使用匹配来求解，后来发现不适合，而后就开始考虑思惟，考虑的是这些奶茶他在必定意义上是等价的，而后我们只要是把本身班级的奶茶给抛出去进行判断处理就能够，每次比较当前剩余的奶茶（抛出本身班级生产的）和第i个班级所须要的奶茶，看起来是没有什么问题的，可是呢，确是wa了，后来队友给我解答疑惑，就是我们以前消费的奶茶须要判断一下，由于他们虽然是等价的，可是呢在对于第i的班级的时候，他有自身的制约因素，就是假设以前的奶茶都是消耗的别的班级的，那么剩下给这个班级的就会比实际状况剩余的少，由于本身班级的不能够消耗本身生产的奶茶，因此须要进行一下处理，那么就假设以前消耗的奶茶都是当前这个班级所生产的，那么留下了能够给这个班级使用的奶茶就会变得更多。

ac代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;  4 typedef long long ll;  5 const int N=1e6+10;  6 ll a[N],b[N];  7 int n;  8 int main()  9 { 10     int T; 11     scanf("%d",&T); 12     while(T--) 13  { 14         scanf("%d",&n); 15         ll sb=0,ans=0; 16         for(int i=1;i<=n;i++) 17  { 18             scanf("%lld%lld",&a[i],&b[i]); 19             sb+=b[i]; 20  } 21         for(int i=1;i<=n;i++) 22  { 23             ll t=max(b[i]-ans,ll(0)); 24             ll z=min(sb-t,a[i]); 25             ans+=z; 26             sb-=z; 27  } 28         printf("%lld\n",ans); 29  } 30     return 0; 31 }