蒟蒻求助cfC题
  • 板块学术版
  • 楼主Stevehim
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/1/9 00:33
  • 上次更新2023/10/24 05:06:03
查看原帖
蒟蒻求助cfC题
759274
Stevehim楼主2023/1/9 00:33

RT,反正也过不了了... test2怎么也过不去

#include <bits/stdc++.h>
using namespace std;
#define maxn 5000010
int t;
long long n, m;
long long a[maxn];
int num[maxn]; //存取其它选手的num
int num2[maxn]; //备份
int myNum = 0;
int myNum2 = 0;
int cur = 0;

int main() {
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];//存储每个人的准备时间
		}
		//然后开始分类讨论
		
		int temp;
		int temp1 = m;
		for (int i = 1; i <= n; i++) {
			num[i] = i;
			num2[i] = i;
		}
		cur = 1;
		myNum = 0;
		while (cur <= n) {
			if (m < a[cur]) {
				cur++;
			} else {
				myNum++;
				m -= a[cur];
				num[cur]--; //败者次数减一
				cur++;
			}

		}
		sort(num + 1, num + n + 1);
		int index = n + 1;
		temp = 0;
		int mingci = 1;
		num[n + 1] = -maxn;
//		cout << "myNum=" << myNum << endl;
		for (int i = n; i >= 1; i--) {
			if (num[i] < num[i + 1]) {
				mingci += temp;
				temp = 1;
			} else {
				temp ++;
			}
//			cout << "num[i]=" << num[i] << "mingci=" << mingci << "temp=" << temp << endl;
			if (num[i] <= myNum) {
				index = mingci;
				break;
			}
		}
		//倒着搜
		myNum = 0;
		cur = n;
		m = temp1;
		while (cur >= 1) { //从头往后搜,先找大的
			if (m < a[cur]) {
				cur--;
			} else {
				myNum++;
				m -= a[cur];
				num2[cur]--; //败者次数减一
				cur--;
			}
		}
		sort(num2 + 1, num2 + n + 1);
		int index1 = n + 1;
		temp = 0;
		mingci = 1;
		num2[n + 1] = -maxn;
//		cout << "myNum=" << myNum << endl;
		for (int i = n; i >= 1; i--) {
			if (num2[i] < num2[i + 1]) {
				mingci += temp;
				temp = 1;
			} else {
				temp ++;
			}
//			cout << "num2[i]=" << num2[i] << "mingci=" << mingci << "temp=" << temp << endl;
			if (num2[i] <= myNum) {
				index1 = mingci;
				break;
			}
		}
		cout << min(index, index1) << endl;
	}
	return 0;
}

2023/1/9 00:33
加载中...