【题解】Pursuit（模拟）
https://codeforces.com/contest/1530/problem/C
题目描述
You and your friend Ilya are participating in an individual programming contest consisting of multiple stages. A contestant can get between 0 and 100 points, inclusive, for each stage, independently of other contestants.
Points received by contestants in different stages are used for forming overall contest results. Suppose that k stages of the contest are completed. For each contestant, k??k/4? stages with the highest scores are selected, and these scores are added up. This sum is the overall result of the contestant. (Here ?t? denotes rounding t down.)
For example, suppose 9 stages are completed, and your scores are 50,30,50,50,100,10,30,100,50. First, 7 stages with the highest scores are chosen — for example, all stages except for the 22-nd and the 66-th can be chosen. Then your overall result is equal to 50+50+50+100+30+100+50=430.
As of now, nn stages are completed, and you know the points you and Ilya got for these stages. However, it is unknown how many more stages will be held. You wonder what the smallest number of additional stages is, after which your result might become greater than or equal to Ilya's result, at least in theory. Find this number!
输入：
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1000). Description of the test cases follows. The first line of each test case contains a single integer n (1≤n≤10^5) — the number of completed stages.
The second line contains nn integers a1,a2,…,an (0≤ai≤100) — your points for the completed stages.
The third line contains nn integers b1,b2,…,bn (0≤bi≤1000≤bi≤10) — Ilya's points for the completed stages.
It is guaranteed that the sum of nn over all test cases does not exceed 10^5.
输出：
For each test case print a single integer — the smallest number of additional stages required for your result to be able to become greater than or equal to Ilya's result.
If your result is already not less than Ilya's result, print 0.
输入样例
5
1
100
0
1
0
100
4
20 30 40 50
100 100 100 100
4
10 20 30 40
100 100 100 100
7
7 59 62 52 27 31 55
33 35 50 98 83 80 64
输出样例
0
1
3
4
2
题目大意
我和我的朋友Ilya已经进行了n轮比赛，比赛的输赢是看每一轮比赛总分(0 - 100)的和谁大，总分的计算方法是取最高的n?floor(n/4)场比赛的成绩求和(floor表示向下取整数)。现在给出前n轮比赛我的成绩和llya的成绩，问在最好的情况下再进行多少场比赛我的分数可以大于或等于llya，输出最小的比赛场次。如果你的分数已经满足要求就输出0。
思路及代码实现
最好的情况就是在之后的比赛中我总能拿到100分，而Ilya总是0分，用一个while循环不断进行模拟直到我的分数大于等于llya并统计循环了几次，即可得出答案。把我的成绩按照从小到大排列（这样加入了后来的100分后我的成绩依旧是递增的），同理，Ilya的成绩按照从大到小排列。
随着n的增加，n-floor(n/4)会 +1 或者不变。在while循环中，先每次把我的分数加上100，然后判断 n-floor(n/4) 是不变还是 +1。
- 如果+1，我的成绩则不需处理，Ilya的成绩需加上当前最小数（可能不是0，因为一开始n-floor(n/4) < n ）
- 如果不变，我的成绩就减去当前最小值，Ilya的成绩不需处理
C++代码实现
#include
#include
#include
using namespace std;
const int N = 1e6 + 10;//数组范围开1e5会越界
int a[N], b[N];//a[]存放我的得分,b[]存放那谁的得分
bool my_cmp(int a,int b){
return a > b;
}
int main() {
int t;
cin >> t;
while(t--){
int n;
scanf("%d", &n);
int x = n - floor(n * 1.0 / 4);
for (int i = 0; i < n;i++) scanf("%d", &a[i]);
for (int i = 0; i < n;i++) scanf("%d", &b[i]);
sort(a, a + n);//我的分数从小到大排列（用默认sort
sort(b, b + n, my_cmp);//那谁从大到小排列
int s1 = 0, s2 = 0;
for (int i = n - 1; i >= n - x; i--) s1 += a[i];//计算我的得分
for (int i = 0; i < x; i++) s2 += b[i];//计算那谁的得分
int ans = 0, pos1 = n - x, pos2 = x;
//用pos记录当前最低分的下标记
while(s1n时为0）
else s2 += b[pos2++];
//答案+1
ans++;
}
printf("%d\n", ans);
}
return 0;
}