FJNU 1157 Fat Brother’s ruozhi magic（胖哥的弱智术）
Time Limit: 1000MS Memory Limit: 257792K
|
【Description】 |
【题目描述】 |
|
Fat Brother is a powerful magician. Both he and his enemy has N soldiers and each soldier has IQ. When two soldier is in PK, the one whose IQ is exactly higher than the another one will win. He can use ruozhi magic to decrease his enemy’s soldiers’ IQ, using ruozhi magic one time, all of his enemy’s soldiers’ IQ will decrease 1. Fat Brother is a perfectionists, so he want his all soldiers to win and uses ruozhi magic at least the number of times. So you should help Fat Brother calculate how many times he should use ruozhi magic？ |
胖哥是一位强力法师。他和他的敌人都有N个小兵，每个小兵拥有一定IQ。当小兵两两PK时，IQ较高者胜。他能用弱智术减少敌方小兵的IQ，弱智术每次能减少1点敌方所有小兵的IQ。胖哥是个完美主义者，因此他希望己方小兵完胜并尽可能少地使用弱智术。所以就由你来帮胖哥算算他最少需要使用的弱智术的次数是多少？ |
|
【Input】 |
【输入】 |
|
There are multiple test cases. The first line of input contains an integer T (T <= 20) indicating the number of test cases. For each test case: The first line contains one integer N (1 <= N <= 100000) means number of soldiers. The next line contains N number Ai means Fat Brother’s soldiers IQ, The next line contains N number Bi means enemy’s soldiers IQ, Ai and Bi fit in 32-bits signed integer |
多组测试用例。 第一行是一个整数T(T <= 20)表示测试用例的数量。对于每个测试用例： 第二行是一个整数N(1 <= N <= 100000)表示小兵的数量。 下一行有N个数Ai，表示胖哥小兵的IQ。 下一行有N个数Bi，表示胖哥小兵的IQ。 Ai与Bi在32为整数间。 |
|
【Output】 |
【输出】 |
|
Each case print a number means at least the number of times Fat Brother should use ruozhi magic |
每个用例输出胖哥弱智术的最小使用次数。 |
|
【Sample Input - 输入样例】 |
【Sample Output - 输出样例】 |
|
2 5 1 3 2 4 5 3 3 3 3 3 3 2 -9 -5 5 -2 -7 |
3 4 |
|
【Hint】 |
【提示】 |
|
First case, use 3 times ruozhi magic, his enemy’s soliders’ IQ will become 0 0 0 0 0, all enemy’s soliders’ IQ lower than Fat Brother’s, So all Fat Brother’s soliders will win Second case, use 4 times ruozhi magic, his enemy’s soliders’ IQ will become 1 -6 -11, So Fat Brother’s first solidier win enemy’s first solidier, second win third, third win second. |
第一个用例， 使用3此弱智术，敌方小兵IQ将变成0 0 0 0 0，所有敌方小兵的IQ低于胖哥的，因此己方小兵获胜。 第二个用例， 使用4次弱智术，敌方小兵IQ将变成1 -6 -11，使用胖哥的第一个小兵完胜敌方第一个，第二个完胜第三个，第三个完胜第二个。 |
【题解】
从测试样例可以看出我方拥有其两两PK的选择权，又需要全胜，因此上等马VS上等马，下等马VS下等马，排个序就好了。
【代码 C++】
#include<cstdio>
#include <algorithm>
#define LL long long
LL s1[], s2[];
int main(){
int t, n, i;
LL sum;
while (~scanf("%d", &t)){
while (t--){
scanf("%d", &n);
for (i = ; i < n; ++i) scanf("%lld", &s1[i]);
for (i = ; i < n; ++i) scanf("%lld", &s2[i]);
std::sort(s1, s1 + n); std::sort(s2, s2 + n);
for (i = sum = ; i < n; ++i){
if (s1[i] + sum <= s2[i]) sum += s2[i] - s1[i] - sum + ;
}
printf("%lld\n", sum);
}
}
return ;
}