网页设计基础项目考核,班级优化大师,免费制作个人网站,湖北省建设厅网站a群Berland军队正在为一场大型阅兵式做准备。已经决定#xff0c;参与其中的士兵将被分为k行#xff0c;所有行都将包含相同数量的士兵。 当然#xff0c;并不是每一次把士兵排成k排都是合适的。同一排中所有士兵的身高差异不应超过1。每个士兵的身高是一个介于1和n之间的整数。…Berland军队正在为一场大型阅兵式做准备。已经决定参与其中的士兵将被分为k行所有行都将包含相同数量的士兵。 当然并不是每一次把士兵排成k排都是合适的。同一排中所有士兵的身高差异不应超过1。每个士兵的身高是一个介于1和n之间的整数。 对于每一个可能的高度你都知道有这个高度的士兵人数。要进行阅兵你必须选择参加阅兵的士兵然后将所有选定的士兵排列成k排以满足以下两个条件 1.每排士兵人数相同 2.没有一排士兵的身高相差2英尺或2英尺以上。
计算可以参加阅兵式的最大士兵人数。
输入 第一行包含一个整数t1 ≤ t ≤ 10000——测试用例的数量。然后是测试用例。 每个测试用例以一行开始该行包含两个整数n和k1 ≤n ≤ 300001 ≤ k ≤ 1e12——分别是阅兵式中不同高度的士兵数量和士兵排数。 每个测试用例的第二行也是最后一行包含n个整数c1c2。。。cn0 ≤ ci≤ 1e12其中ci是Berland军队中身高为i的士兵人数。 保证所有测试用例的n之和不超过30000。
输出 对于每个测试用例打印一个整数——可以参加游行的最大士兵人数。
Input 5 3 4 7 1 13 1 1 100 1 3 100 2 1 1000000000000 1000000000000 4 1 10 2 11 1
Output 16 100 99 2000000000000 13
解析
主要是二分的check函数别写错了
#include bits/stdc.h
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pairint,int PII;
const double PIacos(-1.0);
const int N2e610;
int n,k;
int a[N];
bool check(int x)
{int num0;int cnt0;for (int i1;in;i){num (a[i]cnt) /x;if (a[i]cntx) cnta[i]; //当不够一排的时候就从当前开始之前的 cnt 人数在下次计算时高度差值就为 2 了所以得舍.else cnt(a[i]cnt) %x;}return numk;
}
void solve()
{cinnk;int sum0;for (int i1;in;i){cina[i];sum a[i];}int rsum/k10;int l0;while (lr){int midlr11;if (check(mid)) lmid;else rmid-1;}coutl*kendl;
}
signed main()
{ios;int t;cint;while (t--) solve();return 0;
}
