Cf早期评分虚高
查看原帖
Cf早期评分虚高
453555
qW__Wp楼主2024/10/19 10:25

标题只是骗你进来的对不起我错了,但是这哪有蓝啊

求调,WA on #23,link

Code:

#include <bits/stdc++.h>
//#define int long long
#define INF 0x3fffffff
#define INFF 1e18
#define endl '\n'
#define lson id << 1
#define rson id << 1 | 1
#define LL long long
#define ULL unsigned long long

using namespace std;

const int N = 2e5 + 5;

int n, T;
vector<int> ansa, b;

struct Node {
	int a, t, id;
} a[N];

bool cmp(Node x, Node y) {
	return x.t != y.t ? x.t < y.t : x.a < y.a;
}

bool check(int x) {
	int res = 0, sum = 0;
	b.erase(b.begin(), b.end());
	for (int i = 1; i <= n; i ++) {
		if (a[i].a >= x) {
			if (sum + a[i].t <= T) {
				sum += a[i].t;
				res ++;
				b.push_back(a[i].id);
//				printf("x = %d, id = %d, a = %d, t = %d\n", x, a[i].id, a[i].a, a[i].t);
			} else break;
		}
	}
	return res >= x;
}

signed main() {
	cin >> n >> T;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].a >> a[i].t;
		a[i].id = i;
	}
	sort(a + 1, a + n + 1, cmp);
	int l = 0, r = n, ans = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			l = mid + 1, ans = mid;
			ansa = b;
		}
		else r = mid - 1;
	}
	cout << ans << endl << ansa.size() << endl;
	for (int i = 0; i < ansa.size(); i ++) {
		cout << ansa[i] << ' ';
	}
//	cout << endl << "size:" << ansa.size();
	return 0;
}
2024/10/19 10:25
加载中...