当前位置: 代码迷 >> 综合 >> codeforces 1530C Pursuit
  详细解决方案

codeforces 1530C Pursuit

热度:32   发布时间:2023-12-02 23:18:15.0

链接:

https://codeforces.com/problemset/problem/1530/C

题意:

总共n长比赛,取n?n/4场最高分之和,求最少还要几场比赛自己的分数才能高于Ilya。

本题可以先将二者的分数都排序,自己的正序,llya的逆序。之后while循环,直到自己的分数大于llya退出循环,每次都让自己接下来的比赛得100分,llya的比赛得0分。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
typedef long long ll;
int a[1000003];
int b[1000003];
bool cmp(int a, int b) {return a > b;
}
int main() {int T;cin >> T;while (T--) {memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));int n;cin >> n;int cntm = n - n / 4;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}sort(a, a + n);sort(b, b + n, cmp);int suma = 0, sumb = 0;for (int i = n / 4; i < n; i++) {suma += a[i];}for (int i = 0; i < cntm; i++) {sumb += b[i];}int ans = 0;int position = n / 4;while (suma < sumb){ans++;n++;a[n - 1] = 100;b[n - 1] = 0;suma += 100;int temp = cntm;cntm = n - n / 4;if (temp == cntm) {suma -= a[position++];}else {sumb += b[temp];}}cout << ans;cout << endl;}
}