hdu 4768 Flyer(二分）

題目鏈接：hdu 4768 Flyer

題目大意：給出n，表示有n種廣告，然後每種廣告有a，b，c三個值，表示分發的對象有a，a+c，a+2*c...a+k*c.(a+k*c <= b && a+(k+1)*c > b).然後收到廣告數為奇數的同學是不幸運的，如果沒有人收到廣告數為奇數，輸出DC Qiang is unhappy！，否則輸出不幸運同學的序號以及收到的廣告數，樣例確保至多一人為奇數。

解題思路：二分，首先要確定，如果在[l,r]這個區間上有一個人的廣告數為奇數，那麼總的廣告數也為奇數。所以可以二分首先確定l~r這個區間上有一個人是不幸運的，然後二分mid = （l+r)/2，如果mid~r這個區間為奇數的話，l = mid+1，否則r = mid。然後就是統計一個區間中的廣告數時要注意，並不是區間長度len，len/d+1（d為當前考慮的廣告分發間距）就是廣告數，要與分發的起始位置相關聯。

#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int N = 20005;
const ll INF = (1<<31)-1;
struct ad {
	ll a, b, c;
}d[N];
int n, m;
ll l, r;

void init () {
	l = INF; r = 0;

	for (int i = 0; i < n; i++) {
		cin >> d[i].a >> d[i].b >> d[i].c;
		l = min(l, d[i].a);
		r = max(r, d[i].b);
	}
}

ll judge (ll k) {
	ll c = 0;
	for (int i = 0; i < n; i++) {
		ll x = min(r, d[i].b) - d[i].a;
		ll y = min(k, d[i].b) - d[i].a;
		if (x >= 0)
			c += (x/d[i].c + 1);
		if (y >= 0)
			c -= (y/d[i].c + 1);

	}
	return c;
}

ll solve () {
	while (l < r) {
		ll mid = (l+r) / 2;
		if (judge(mid)&1) l = mid+1;
		else r = mid;
	}
	return l;
}

int main () {
	while (scanf("%d", &n) == 1) {
		init ();
		if (judge(l-1)&1) {
			ll ans = solve(), c = 0;
			for (int i = 0; i < n; i++) {
				if (ans > d[i].b) continue;
				ll x = ans - d[i].a;
				if (x >= 0&&x%d[i].c == 0) c++;
			}
			cout << ans << " " << c << endl;
		} else
			printf("DC Qiang is unhappy.\n");
	}
	return 0;
}