84求调
查看原帖
84求调
921173
ywk2011楼主2024/11/25 22:33

2、3两个点WA 跟没有离散化有关吗

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7;
__int128 mod = 1e7+114514;
typedef struct M{
	int id;
	int data;
}M;
int n,m;
M mylist[N];
int t[N];
int l,r;
int cnt;
int ans = 2e9;
map<int,bool> mp;
bool cmp(M a,M b){
	return a.data < b.data;
}
signed main(){
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>mylist[i].data>>mylist[i].id;
		mylist[i].id %= mod;
	}
	sort(mylist+1,mylist+1+n,cmp);
	for(int i = 1;i<=n;i++){
		if(mp[mylist[i].id] == false){
			m++;
			mp[mylist[i].id] = true;
		}
	}
	l = 1;
	r = 1;
	while(r <= n+1){
		if(cnt < m){
			if(t[mylist[r].id] == 0){
				cnt++;
			}
			t[mylist[r].id]++;
			r++;
		}else{
			if(t[mylist[l].id] > 1){
				t[mylist[l].id]--;
				l++;
			}else{
				if(ans > mylist[r-1].data-mylist[l].data){
					ans = mylist[r-1].data-mylist[l].data;
				}
				cnt--;
				t[mylist[l].id]--;
				l++;
			}
			
		}
	}
	cout<<ans;
    return 0;
}
2024/11/25 22:33
加载中...