【题目大意】
【思路分析】
个人感觉这题挺妙的，一开始没看出来是二分，但有了二分的思路之后就很简单了。
首先看到这题第一反映想到暴力，直接开数组统计每个位置的人数，但是这样数组就太大了，所以我们考虑用函数$cal(x)$表示位置$1～x$之间的总人数。因为已知人数为奇数的位置要么没有，要么只有一个，所以先找到左右边界，算出$mid$和$cal(mid)$，如果$cal(mid)$为奇数，则符合要求的位置在$l～mid$之间，否则在$mid+1～r$之间。还要注意一开始先算一下$cal(r)$，若为偶数，则不存在满足条件的位置。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #define rg register 4 #define ll long long 5 #define go(i,a,b) for(rg ll i=a;i<=b;i++) 6 using namespace std; 7 const int N=200002; 8 ll T,n,S[N],D[N],E[N],pos,num; 9 ll cal(ll d){ 10 ll s=0; 11 go(i,1,n){ 12 if(S[i]>d) continue; 13 s+=(min(E[i],d)-S[i])/D[i]+1; 14 } 15 return s; 16 } 17 int main(){ 18 scanf("%lld",&T); 19 while(T--){ 20 scanf("%lld",&n); 21 ll maxn=0; 22 ll minn=1e9; 23 go(i,1,n){ 24 scanf("%lld%lld%lld",&S[i],&E[i],&D[i]); 25 maxn=max(maxn,E[i]); 26 minn=min(minn,S[i]); 27 } 28 if(cal(maxn)%2==0) {printf("Poor QIN Teng:(\n");continue;} 29 ll l=minn,r=maxn; 30 while(l<r){ 31 ll mid=(l+r)/2; 32 if(cal(mid)%2!=0) r=mid; 33 else l=mid+1; 34 } 35 printf("%lld %lld\n",l,cal(l)-cal(l-1)); 36 } 37 return 0; 38 }
原文：https://www.cnblogs.com/THWZF/p/11262859.html
