为什么不是按t2-t1排序
查看原帖
为什么不是按t2-t1排序
755850
Sword_wielder楼主2023/9/2 14:00

90分:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
struct node {
	int t1, t2;
} a[N];
bool cmp (node a, node b) {
	return a.t2 < b.t2;
}
int TIME = 0;
priority_queue <int> q;
signed main () {
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i ++) {
		cin >> a[i].t1 >> a[i].t2;
		a[i].t2 -= a[i].t1;
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1 ; i <= n ; i ++)
		if (a[i].t2 >= 0) {
			if (a[i].t2 >= TIME) {
				TIME += a[i].t1;
				q.push(a[i].t1);
			} else if (!q.empty()) {
				if (a[i].t1 < q.top()) {
					TIME = TIME - q.top() + a[i].t1;
					q.pop();
					q.push(a[i].t1);
				}
			}
		}
	cout << q.size();
	return 0;
}


满分:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
struct node {
	int t1, t2;
} a[N];
bool cmp (node a, node b) {
	return a.t2 < b.t2;
}
int TIME = 0;
priority_queue <int> q;
signed main () {
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i ++) {
		cin >> a[i].t1 >> a[i].t2;
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1 ; i <= n ; i ++)
		if (a[i].t2 >= 0) {
			if (a[i].t2 >= TIME + a[i].t1) {
				TIME += a[i].t1;
				q.push(a[i].t1);
			} else if (!q.empty()) {
				if (a[i].t1 < q.top()) {
					TIME = TIME - q.top() + a[i].t1;
					q.pop();
					q.push(a[i].t1);
				}
			}
		}
	cout << q.size();
	return 0;
}


2023/9/2 14:00
加载中...