CodeForces-650B Image Preview

题意

手机里有n张图片，打开相机出现的是第一张，第一张右滑得到第n张，同理第n张左滑得到第1张，翻页耗费a秒，看照片耗费1s，但是照片有横屏的竖屏的，如果是横屏的需要翻转一下，翻转需要的时间为bs，如果某张照片是已经看过的，可以不看，否则必须看完才能左滑或者右滑（注意），现在你有t秒时间，最多可以看多少张照片。

思路

就是一个模拟题，两种看法，先左滑，然后二分判断右滑可以再看多少张，先右滑再二分左滑可以再看多少张。

代码写得有点恶心。

代码

//#include<bits/stdc++.h>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<string>

#include<math.h>

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N=1e6+10;

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

const double eps=1e-14;

char str[N];

int pre[N],suf[N];

int n,a,b,t;

int check(int aga,int en,int rel)

{

    int tur=(en-aga)*a;

    int roa=pre[en]-pre[aga-1];

    int rea=en-aga+1;

    return (tur+roa+rea)<=rel;

}

int main()

{

    scanf("%d%d%d%d",&n,&a,&b,&sum);

    scanf("%s",str+1);

    for(int i=n+1;i<=2*n;i++)

        str[i]=str[i-n];

    for(int i=1;i<=2*n;i++)

        pre[i]=pre[i-1]+b*(str[i]=='w');//旋转

    int maxn=0;

    for(int i=2;i<=n;i++)//先向左再向右，从第n+1张左滑到第i张

    {

        int time=(n+1-i)*a+pre[n+1]-pre[i-1]+n+2-i;//看到第i张花费的时间

        if(time>sum) continue;

        int rel=sum-time-(n+1-i)*a-a;//剩余还有多少时间从第n+2张往右看

        int l=n+2,r=n+i-1,ans=0;//二分

        while(l<=r)

        {

            int mid=(l+r)/2;

            if(check(n+2,mid,rel))

            {

                ans=mid-n-1;

                l=mid+1;

            }

            else r=mid-1;

        }

        maxn=max(ans+(n+2-i),maxn);

    }

    for(int i=n+1;i<=2*n;i++)//从第n+1张右滑到第n+i张，再左滑

    {

        int time=a*(i-n-1)+(i-n)+pre[i]-pre[n];

        if(time>sum) continue;

        int rel=sum-time-(i-n-1)*a-a;//翻到第n页，还剩多少时间

        int l=i-n+1,r=n,ans=0;//二分

        while(l<=r)

        {

            int mid=(l+r)/2;

            if(check(mid,n,rel))

            {

                ans=n-mid+1;

                r=mid-1;

            }

            else l=mid+1;

        }

        maxn=max(i-n+ans,maxn);

    }

    printf("%d\n",maxn);

    return 0;

}

博客

巴特西

CodeForces-650B Image Preview 二分+模拟

CodeForces-650B Image Preview

题意

思路

代码

最新文章

热门文章