博客

题目链接：

https://cn.vjudge.net/problem/ZOJ-4062

具体思路，二分法求最大值，然后看当前的值是不是符合情况，然后求出一个最优值。

AC代码：

#include<iostream>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
# define maxn 200000+100
# define eps 1e-6
ll a[maxn];
ll n,m;
bool check(ll ans)
{
if(ans==0)return true;// 如果求的最优值为0，直接return ，因为肯定符合。
    ll step,temp=0;
    ll tt=m;
    for(int i=1; i<=n; i++)
    {
        if(i==n&&a[i]*temp>=ans)return true;//如果最后一个的话，不需要往后走，也就是先直接判断。
        if(a[i]*(temp+1)>=ans)temp=0;//如果在之前的循环当前的位置的值已经符合的话，就不需要走了。
        else
        {
            temp=(ans-a[i]*(temp+1))/a[i];//需要来回多少次才能满足情况。
            if((ans-a[i]*(temp+1))%a[i])temp++;//如果有余数也需要加上。
        }
        step=temp*2+1;//因为是来回，所以需要*2，两个棋子之间的步数是1.
        tt-=step;
        if(tt<0)return false;
    }
    return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
        }
        ll l=0,r=1e17+1;
        if(m==0)
        {
            printf("0\n");
            continue;
        }
        while(r>=l)
        {
            ll mid=(l+r)>>1;
            if(check(mid))l=mid+1;
            else r=mid-1;
        }
        printf("%lld\n",r);
    }
    return 0;
}