网站开发毕业答辩ppt,做房产必知的发布房源网站,安徽网站建设认准-晨飞网络,上海专业建网站Defuse the Bombs Gym - 102822D
题目#xff1a;
给你n个数#xff0c;现在每轮会有三个操作#xff1a; 1.选择一个数#xff0c;使他加一 2.所有数减一 3.当有一个数变成负数时结束操作#xff0c;否则回到第一步 问最多能进行几次第一步#xff1f;
题解#xff…Defuse the Bombs Gym - 102822D
题目
给你n个数现在每轮会有三个操作 1.选择一个数使他加一 2.所有数减一 3.当有一个数变成负数时结束操作否则回到第一步 问最多能进行几次第一步
题解
题目相当于在问最多能进行几轮 这个题不大好想我们可以转换下思路题目说的是先选一个数加1然后其他数减一然后问最多能加几轮那我们可不可以这么想我们先将所有数减最后再加看是否所有数都大于等于0。我们设最多加了x轮那么所有数都要减x然后我们看所有比0小的数他们与0的差的绝对值的和是多少因为我们要用x去补如果x大于等于和说明当前x轮可以完成这个x可以用二分去寻找 是否符合单调性呢题目是符合的
代码
#include bits/stdc.h
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int maxn2e59;
ll a[maxn];
int n;
bool check(ll x){ll sum0;for(int i1;in;i){if(a[i]x)sum(x-a[i]);}if(sumx)return 1;return 0;
}
int main(){int t;cint;int cas0;while(t--){cinn;for(int i1;in;i)cina[i];ll l1,r2e10;while(lr){ll midlr1;if(check(mid))lmid1;else rmid;}printf(Case #%d: %d\n,cas,r);}return 0;
}
