周期性+二分

注意点①：周期是x+1，并不是x，但是我第一次用x二分出来r-1碰巧过了，但是一开始我没想通。

注意点②:n可能会小于d,所以存在min函数。

#include<iostream>
#include<algorithm>
#define ll long long
const int N = 1e6 + 5;
ll t, n, c, d, sum;
ll a[N];
using namespace std;

bool check(ll x) {
	ll frequency = d / (x + 1);//周期的次数
	ll remainder = d % (x + 1);//多余出来的天数
	ll T = 0, Tr = 0;
	for (ll i = 1; i <= min(x + 1, n); ++i)T += a[i];
	for (ll i = 1; i <= min(remainder, n); ++i) Tr += a[i];
	return T * frequency + Tr >= c;
}
int main() {
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld%lld%lld", &n, &c, &d);
		for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
		sort(a + 1, a + 1 + n, greater<ll>());
		if (a[1] * d < c) {
			printf("Impossible\n");
			continue;
		}
		sum = 0;
		for (int i = 1; i <= min(n, d); ++i)sum += a[i];
		if (sum >= c) {
			printf("Infinity\n");
			continue;
		}
		ll l = 0, r = d + 1, mid;
		while (l < r) {
			mid = (l + r + 1) >> 1;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		printf("%lld\n", l);
	}
	return 0;
}

题解

http://t.csdn.cn/Kf9DZ

题目翻译

这里有n个任务，如果你完成了第i个任务，你将获得ai个硬币，你每天最多只能完成一个任务，然而，你完成了一个任务后，你在k天内不能完成相同的任务，例如（如果 k=2 ，你在第一天完成任务1，之后你不能在第二天第三天也完成它，但是你可以在第四天再次完成他） 你被给予了两个int类型的数c，d，找到k的最大值使得你在d天内能至少获得c的硬币，如果不存在k，输出“Impossible”，如果k能任意大的话，输出“​Infinity​”。