CCF-CSP 202012-2 期末预测之最佳阈值

直接暴力做只能过70%，想了半天，一开始认为是前缀和，后来又想前缀和怎么处理相同分数但有0有1的情况呢？没想清楚后作罢。看网上题解用的确实是前缀和，没考虑相同分数，直接前缀和。同时用集合跳过已统计过的分数。
想想确实，如果相同分数有0有1，在第一个分数处计算 i-1-prefix[i-1] + prefix[n-1]-prefix[i-1]就能统计出分数之下没及格但分数及之上及格的人数。

#include
#include
#include
#include
#include
using namespace std;

int main() {
	// prefix sum
	int n, nn;
	cin >> n; nn = n;
	vector<pair<int,int>> p;
	vector<int> prefix(n+1, 0);
	set<int> st;
	
	while(nn--){
		int a, b;
		cin >> a >> b;
		p.push_back(make_pair(a, b));
	}
	
	sort(p.begin(), p.end());
	for(int i = 1; i <= n; i ++){
		prefix[i] = prefix[i-1] + p[i].second;
	}
	
	int ans = 0, theta = 0;
	for(int i = 1; i <= n; i ++){
		if(st.count(p[i].first)) continue;
		st.insert(p[i].first);
		int tmp = i-1-prefix[i-1] + prefix[n] - prefix[i-1];
		if(tmp >= ans){
			ans = tmp;
			theta = p[i].first;
		}
 	}
 	cout << theta << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39