2018年ACM-ICPC青岛区域赛 E题 Plants vs. Zombies
发布时间
阅读量：
阅读量
Sample Input
2
4 8
3 2 6 6
3 9
10 10 1
Sample Output
6
4
题意：
T组测试案例
n株植物与机器人步数m（即浇水次数）
机器人沿东西方向直线运动
路径描述：从室内出发经过依次排列的n株植物到达花园区域之外
每次移动均需进行浇水操作
各株植物的增长速率各异，并以浇灌次数影响其生长情况
整个园艺布局的安全性主要由最弱环节决定
确定一种最优路径以最大化园艺布局的安全性
案例：4 8
思路说明
- 约束函数c(x)定义为在m次迭代内使每一株植物的长度不低于x。
- 变量x的初始取值范围设定为[0, 1e17]。
- 当满足约束函数c(x)时，则将下界提升至mid+1的位置即可确定全局最优解的最低界限。
条件c(x)的判断函数实现：
当最小值等于零时返回true。
计算达到最小值所需浇水次数的公式为num=(m+a[i]-1)/a[i]。
各点之间的步数计算方法是将相邻两点之间的跳跃次数相加。
b数组用于存储机器人在各个关键节点处所经历的跳跃次数。
当所有植物均被浇过水时基础跳跃次数设定为一并递增。
首先将当前节点与其前驱节点之间的跳跃次数记录下来；然后将该数值与基础数值加一进行对比；如果当前数值较小则更新基础数值；最后将两者的差额记录到下一个相邻节点上。
当处理到最外侧植物时无需考虑其是否达到目标状态；在循环结束时需添加判断条件以确保最后一个额外位置未被错误处理。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 100100;
int N;
ll M;
int a[MAXN];
ll b[MAXN];
bool judge(ll m)
{
if(m==0)
return true;
for(int i=0; i<N+1; i++)
b[i]=0;
for(int i=0; i<N; i++)
{
ll num=(m+a[i]-1)/a[i];
if(i==N-1&&b[i]>=num)
break;
b[i]++;
if(b[i]<num)
{
b[i+1]=num-b[i];
b[i]=num;
}
}
ll sum=0;
for(int i=0; i<N+1; i++)
{
sum+=b[i];
if(sum>M)
return false;
}
return true;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&N,&M);
for(int i=0; i<N; i++)
scanf("%d",&a[i]);
ll l=0,r=1e17;
while(l<=r)
{
ll mid=(r-l)/2+l;
if(judge(mid))
l=mid+1;
else
r=mid-1;
}
printf("%lld\n",l-1);
}
return 0;
}全部评论 (0)
还没有任何评论哟~