题意

https://vjudge.net/problem/CodeForces-1256C

有一条宽度为n的河。河的左岸编号为0，右岸编号为n+1。河流上还有m个木制平台，第i个平台的长度为ci（所以说第i个平台占据河流的ci个连续位置）。保证平台长度的总和不超过n。

你正站在0（左岸），并且想到达右岸即n+1的位置。如果您站在位置x，则可以跳到[x+1，x+d]范围内的任何位置。但是，你只能跳到木质平台上（ 即不能下水 ）。例如，如果d=1，则只能跳到下一个位置（如果这个位置上有木制平台）。您可以假设单元格0和n+1属于木制平台。

您可以将任意平台向左或向右移动任意次数（也可以不移动），只要它们彼此不重叠（但两个平台可以挨在一起）。也就是说你不能更改平台的相对顺序。

请注意，你应该先移动平台再跳跃（一旦你出发后，你就不能再移动平台了）。

例如，如果n=7，m=3，d=2和c=[1,2,1]，这就是从左岸跳到右岸的方法之一：

思路

题目开始读错了，坑爹。注意每个板子的顺序是不能改变的，而且每个板子都要用上。因为我们的首要目标是到达n+1，所以贪心跳d步，但我们也要考虑留给放板子的空位够不够，所以如果当前位置+d+未放板子的长度和-1<=n，那么我们要跳到当前位置+d；否则跳到n-未放板子长度和+1，在每次跳到的位置放板子，最后判断能否跳到n+1。

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=2005;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

int main()

{

    std::ios::sync_with_stdio(false);

    int n,m,d;

    while(cin>>n>>m>>d)

    {

        int w[N],sum=0;

        for(int i=1; i<=m; i++)

        {

            cin>>w[i];

            sum+=w[i];

        }

        int s=0,t=1;

        int ans[N];

        memset(ans,0,sizeof(ans));

        int flag=0;

        while(s<=n)

        {

            //      cout<<"s:"<<s<<endl;

            if(s+d+sum-1<=n)

                s+=d;

            else

            {

                s=n-sum+1;

            }

            if(s>=n+1)

            {

                break;

            }

            //    cout<<s<<endl;

            if(t<=m)

            {

                for(int i=s; i<s+w[t]; i++)

                {

                    ans[i]=t;

                }

                s=s+w[t]-1;

                sum-=w[t];

                t++;

            }

            else

            {

                flag=1;

                break;

            }

        }

        if(flag)

        {

            cout<<"NO"<<endl;

        }

        else

        {

            cout<<"YES"<<endl;

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

            {

                cout<<ans[i]<<" ";

            }

            cout<<endl;

        }

    }

    return 0;

}

巴特西

CodeForces - 1256C （思维+贪心）

题意

思路

代码

最新文章

热门文章