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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>

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;
}

hdu 4768 Flyer(二分）,布布扣,bubuko.com

hdu 4768 Flyer(二分）

原文：http://blog.csdn.net/keshuai19940722/article/details/20862753