题目大意

给出一条防线上的防具布置情况，求防线的第一个破绽位置与该位置上的防具数量。

题目分析

记\(S(x)\)表示\(0~x\)的位置上一共有多少防具，对于每组防具，如果\(s_i\)在x之前，那么就把\(min(x,d_i)\)之前的防具累加，一直累加到n求出\(S(i)\),时间复杂度为\(O(n)\)。
特判：若\(S(2^{31}-1)\)为偶数，则整道防线没有破绽。
设破绽的位置为\(P\)，故只有\(P\)上有奇数个防具，其他位置上都有偶数个防具，则对于所有的\(x<P\)，\(S(x)\)均为偶数，对于所有的\(x>=P\)，\(S(x)\)均为奇数。
考虑二分答案，若\(S(mid)\)为奇数，则答案必定在\(mid\)或者\(mid\)之前，即令\(r=mid\);若\(S(mid)\)为偶数，则答案必定在\(mid\)之后，即令\(l=mid+1\)。
时间复杂度为\(O(32n)\)。

Code

#include<iostream>
#include<cstdio>
#define inf 2147483647
#define sco 200010
using namespace std;
int T,n,s[sco],e[sco],d[sco],v[sco],f[sco];
int S(int x){
	int ans=0;
	for(int i=1;i<=n;++i){
		if(s[i]<=x) ans+=(min(x,e[i])-s[i])/d[i]+1;
	}
	return ans;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d%d%d",&s[i],&e[i],&d[i]);
		}
		if(S(2147483647)%2==0){printf("There‘s no weakness.\n");continue;}
		int l=1,r=2147483647,mid;
		while(l<r){
			mid=(1ll*l+1ll*r)>>1;
			if(S(mid)&1)r=mid;else l=mid+1;
		}
		printf("%d %d\n",l,S(l)-S(l-1));
	}
	return 0;
}

YBTOJ:防具布置

原文：https://www.cnblogs.com/ssllhj/p/15114413.html