KIDx 的解题报告
题目链接:http://lightoj.com/volume_showproblem.php?problem=1048
题意:给n+1个数,要你通过合并使其变成k+1个数,要求令这k+1个数的最大值最小,另外输出时尽量让前面的大
#include <iostream>
using namespace std;
#define M 1005
int n, a[M], k;
bool judge (int key) //暴力检验
{
int i = 0, num = 0;
while (i < n)
{
int tp = a[i++];
if (tp > key) //以key为最大值,因此需检验每个元素是否<=key
return false;
for ( ; i < n; i++)
{
if (tp + a[i] <= key)
{
tp += a[i];
num++;
}
else break;
}
}
if (num >= n - k) //合并次数要符合,不可放到上面的for循环里
return true; //因为还要满足每个元素都<=key
return false;
}
int main ()
{
int t, cc = 1, l, r, mid, i, num;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &k);
n++, k++;
l = r = 0;
for (i = 0; i < n; i++)
{
scanf ("%d", a+i);
r += a[i];
}
while (l < r) //二分枚举最大值
{
mid = (l+r) >> 1;
if (judge (mid))
r = mid;
else l = mid + 1;
}
printf ("Case %d: %d\n", cc++, r);
i = num = 0;
/***********按题意尽量让前面的大***********/
while (i < n)
{
int tp = a[i++];
if (num < n - k) for ( ; i < n; i++)
{
if (tp + a[i] <= r)
{
tp += a[i], num++;
if (num == n - k) //合并n-k次就不能再合了!
{
i++; break;
}
}
else break;
}
printf ("%d\n", tp);
}
/***********按题意尽量让前面的大***********/
}
return 0;
}
分享到:
相关推荐
使用php做的,google的API客户端的连接程序的例子代码,主要是调用google的API的连接程序,简单全面供给各类学习参考
Loj X 使创建真正的计算单元甚至小型完整处理器成为可能。 除了逻辑门,存储盒和程序阅读器可以集成到电路中。
log4j配置文档,jar包
log4j配置
scicloj.github.com:Scicloj网站
的做题记录 Updates: ...2021.04.03 Luogu4719 Luogu4980 LOJ6538 2021.04.02 Luogu5298 Luogu6619 2021.04.01 Luogu5212 2021.03.21 Luogu4384 2021.03.30 Luogu3804 Luogu6139 2021.03.29 Luogu7470 2021
帕拉iniciarØprojeto EM阵营FOI utilizadoØCOMANDO yarn create react-app moveit --template=typescript ,ONDE moveit éØ诺姆做projetoË --template=typescript éØCOMANDO对inciar-LOJáCOM打字稿。
OICodeRepository zhylj 2019.10.1从今起,我就把代码存在这里,欢迎大家帮我D (c) e (o) b (p) u (y) g代码存放优先级:xxOI =罗古> Poj = loj> Bzoj不太可能会存放在多个地方。请查找同内容题。不保证一定...
包含 mybatis-3.3.0;log4j-1.2.17;junit-4.12;javassist-3.4.GA;hamcrest-all-1.3