ZOJ月赛10，11，第二个

ZOJ月赛10，11，第二个

Cake

Time Limit: 4 Seconds       Memory Limit: 65536 KB

Alice and Bob like eating cake very much. One day, Alice and Bob went to a bakery and bought many cakes.

Now we know that they have bought n

Alice and Bob do n

Now Alice want to know the maximum sum of the value that she can get.

Input

The first line is an integer T

For each test case, the first line is an integer n (1<=n<=800). Note that n

In following n lines, each line contains two integers a[i] and b[i], where a[i] is the value of ith cake that Alice evaluates, and b[i] is the value of ith cake that Bob evaluates. (1<=a[i], b[i]<=1000000)

Note that a[1], a[2]..., a[n] are n distinct integers and b[1], b[2]..., b[n] are n

Output

For each test case, you need to output the maximum sum of the value that Alice can get in a line.

Sample Input

1 6 1 6 7 10 6 11 12 18 15 5 2 14

Sample Output

28

Author: HUA, Yiwe

i

#include #include #include #include #define mem(a,b) memset(a,b,sizeof(a))#define repu(i,a,b) for(int i=a;i<=b;i++)#define sfi(n) scanf("%d", &n)using namespace std;#define MAXN 805struct P{ int a, b, r;}p[MAXN];int n;int A[MAXN], B[MAXN];bool C[MAXN];bool cmp1(P ta, P tb){ return ta.b > tb.b;}bool cmp2(P ta, P tb){ return ta.a > tb.a;}void init(){ B[0] = B[1] = 0; mem(A, 0), mem(C, 0); p[1].r = 1; repu(i, 2, n) { B[i] = B[i - 1] + 1; p[i].r = i; }}int main(){ int T; scanf("%d", &T); while(T--) { sfi(n); repu(i, 1, n) { sfi(p[i].a), sfi(p[i].b); } sort(p + 1, p + 1 + n, cmp1); //repu(i, 1, n) printf("%d %d\n", p[i].a, p[i].b); init(); sort(p + 1, p + 1 + n, cmp2); //repu(i, 1, n) printf("%d %d\n", p[i].a, p[i].b); int ta = 0; int ma, mb; int ans = 0; repu(i, 1, n) { int t = p[i].r; int flag = 0; repu(k, t + 1, n) if(k == t || C[k]){ ma = A[k], mb = B[k]; if(mb - 1 <= ma + 1) { flag = 1; break; } } if(!flag && (A[t] < B[t])) { ta++; C[t] = 1; repu(j, t + 1, n) A[j]++, B[j]--; ans += p[i].a; //printf("%d\n", p[i].a); } if(ta == n / 2) break; } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。