30分 没太懂 为什么WA点和答案会差个1
查看原帖
30分 没太懂 为什么WA点和答案会差个1
1057235
bf29__lj楼主2023/11/12 19:19
#include <cstdio>
#include <algorithm>
#define MAXN 20005
using namespace std;

long long n,pos = 0,npos = 0,res = 0;
int ls[MAXN],rs[MAXN],num[2*MAXN],vir[2*MAXN];

int fd(int k){
	int L = 0,R = npos - 1;
	int m,ans = -1;
	while(L <= R){
		m = L + ((R - L) >> 1);
		if(num[m] >= k){
			ans = m;
			R = m - 1; 
		}else{
			L = m + 1;
		}
	}
	return ans;
}

int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;++i){
		scanf("%d%d",&ls[i],&rs[i]);
		num[pos++] = ls[i];
		num[pos++] = rs[i];
	}
	
	//0 ... n-1	
	sort(num,num + pos);

	npos = 0;
	//1 2 2 2 3 3 3
	for(int i = 0;i < pos;++i){
		if(num[i] != num[i-1]){
			num[npos++] = num[i];
		}
	}
	
	for(int i = 1;i <= n;++i){
		vir[fd(ls[i])]++;
		vir[fd(rs[i])]--;
	}
	
	
	//vir[0] = num[0];
	//printf("%d %d\n",vir[0],num[0]);
	//printf("%d\n",npos);
	//getchar();
	for(int i = 1;i < npos;++i){
		vir[i] += vir[i-1];
		//printf("%d %d\n",vir[i],num[i]);
	}
	int l = 0,r;
	for(int i = 1;i <= npos;++i){
		if(vir[i-1] == 0 && vir[i] > 0)l = i;
		if(vir[i-1] != 0 && vir[i] == 0){
			r = i;
			//printf("%d %d\n",num[l],num[r]);
			res += num[r] - num[l];
		}
	}
	
	printf("%d",res);
	return 0;
}
2023/11/12 19:19
加载中...