3 solutions
Information
- ID
- 6673
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- (None)
- # Submissions
- 31
- Accepted
- 9
- Uploaded By
周期性+二分
注意点①:周期是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;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.