HDU 4768 Flyer 二分
题意：略。
思路：直接二分，因为假设现在在点mid .那么求出[l , mid]的和，如果是奇数，那么那个点肯定在前面的区间，也就是mid = r - 1 ,如果是偶数，则证明在后面的区间，mid = l + 1 。然后更新答案即可。
这种解法很容易想到，但是一直T，理论上复杂度完全可以过，一直很不解。
然后发现，二分过程中mid = l + r >> 1 。这个l + r 可能会爆int ，所以mid 值就是负数了，就一直T。
把mid 改成mid = l + (r - l + 1 ) / 2 即可。
细节把握还是太弱了。
#include <set>#include <map>#include <stack>#include <cmath>#include <queue>#include <cstdio>#include <string>#include <vector>#include <iomanip>#include <cstring>#include <iostream>#include <algorithm>#define Max 2505#define FI first#define SE second#define ll long long#define PI acos(-1.0)#define inf 0x7fffffff#define LL(x) ( x << 1 )#define bug puts("here")#define PII pair<int,int>#define RR(x) ( x << 1 | 1 )#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;inline void RD(int &ret) { char c ; int flag = 1 ; do { c = getchar() ; if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ret = c - '0' ; while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); ret *= flag ;}#define N 22222int A[N] , B[N] , C[N] ;int n ;int main() { while(scanf("%d",&n) != EOF) { int l = inf , r = 0 ; for (int i = 0 ; i < n ; i ++ ) { RD(A[i]) ; RD(B[i]) ; RD(C[i]) ; if(l > A[i]) l = A[i] ; if(r < B[i]) r = B[i] ;// l = min(l , A[i]) ;// r = max(r , B[i]) ; } int ans = inf ; int flag = 0 ; int mid ; while(r >= l) {// mid = l + r >> 1 ; mid = l + (r - l + 1) / 2 ; ll sum = 0 ; for (int i = 0 ; i < n ; i ++ ) { if(C[i] == 0) { if(mid >= A[i]) sum ++ ; continue ; } if(mid >= A[i]) { ll now = min(mid , B[i]) ; sum += (now - A[i]) / C[i] + 1 ; } } if(sum & 1) { r = mid - 1 ; flag = 1 ; if(ans > mid)ans = mid ; } else l = mid + 1 ; } int ss = 0 ; for (int i = 0 ; i < n ; i ++ ) { if(ans <= B[i] && ans >= A[i]) { ss += ((ans - A[i]) % C[i] == 0) ? 1 : 0 ; } } if(!flag)printf("DC Qiang is unhappy.\n") ; else printf("%d %d\n",ans , ss) ; } return 0 ;}