桶排双指针85PTS求教
查看原帖
桶排双指针85PTS求教
470413
NightSky_Chaser楼主2024/10/29 14:13
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 114514;

int n;
int maxData = -1;

long long bucket[MAXN];

int ac();
bool CMP(int, int);

int main() {
	cin >> n;
	long long data;
	memset(bucket, 0, sizeof(bucket));
	for(int i = 1 ; i <= n ; ++i) {
		cin >> data;
		bucket[data]++;
		if(data > maxData) maxData = data;
	}
	int ans = ac();
	printf("%d", ans);
	return 0;
}

bool CMP(int x, int y) {
	return x < y;
}

int ac() {
	int ans = n;
	int p1 = 1, p2 = 1;
	while(1) {
		if(bucket[p1] == 0) {
			p1++;
			continue;
		}
		if(bucket[p2] == 0) {
			p2++;
			continue;	
		}
		if(p1 == p2) {
			p2++;
			continue;
		}
		if(p2 > maxData) break;
		if(bucket[p1] <= bucket[p2]) {
			ans -= bucket[p1];
			bucket[p1] = 0;
			p1++;
		}
		else {
			ans -= bucket[p2];
			bucket[p1] -= bucket[p2];
			p2++;
		}
	}
	return ans;
}
2024/10/29 14:13
加载中...