求调 map+贪心 TLE 11#(悬关)
查看原帖
求调 map+贪心 TLE 11#(悬关)
549846
dpACerFXing楼主2024/3/7 22:10

我的代码最后一个点1.20s T掉了

但是,当我通过一些奇怪的手段拿到每个样例点n的大小时,我发现最后一个点和其他点n的大小本身是差不多的,说明这应该是hack数据

实在不会调了qwq

# include<iostream>
# include<cstdio>
# include<map> 
# define int long long
using namespace std;
const int maxn=1001;
typedef map<int, int>::iterator mi;
int n, a[maxn], ans;
map<int, int> m;
signed main() {
	cin >> n;
	ans=n;
	for(int i=1; i<=n; i++) {
		int k; scanf("%d", &k);
		++m[k];
	}
	int size=m.size();
	while(!m.empty()) {
		mi first=m.begin(), last=m.end();
		int sum=0, temp1=0, temp2=0;
		bool flag=true;
		for(mi it=first; it!=last; it++) {
			if(it->second>=temp2 && it->first==temp1+1 || flag) {
				temp1=it->first; temp2=it->second;
				m[temp1]=temp2-1;
				sum++;
				flag=false;
			} else break;
		}
		ans=min(ans, sum);
		
		mi start=m.begin(), end=m.end();
		for(mi it=start; it!=end; ) {
			if(it->second == 0) m.erase((it++)->first);
			else it++;
		}
	}
	cout << ans << endl;
	return 0;
}
2024/3/7 22:10
加载中...