[CF][贪心] CF 1015D

http://codeforces.com/problemset/problem/1015/D

题意:给定n,k,s,要求在一段[1,n]的线段上走整点,从1开始,每次只能往一个方向走走任意步(但不能不动),然后要求总共走k步走完s,要求输出任意的方案。如果无法做到则输出NO。

首先判断NO是很简单的,要么是要求走的长度太长((n-1)*k>s)),要么是太短(因为每次至少走1步,如果k>s的话就不可能走了)。

如果不是上述两种情况那么就是YES了,但是要如何输出方案?这里用的是贪心的策略:每次尽可能走在当前情况下最长的路(min(n-1,s-k+1))。这样的话走出来的一定是几个n-1的长度和一个介于1到n-1之间的长度,然后之后的都是长度1,这样的话实现起来是相对简单的,因为不需要考虑过多操作。

 

#include
using namespace std;
typedef long long LL;
const int maxn=110005;
const int MOD=20071027;


int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    LL n,k,s;
    int cur=1;
    cin>>n>>k>>s;
    if((n-1)*ks)
        printf("NO\n");
    else
    {
        printf("YES\n");
            while(k>0)
            {
                int l=min(n-1,s-k+1);
                cur=cur-l>0?cur-l:cur+l;
                printf("%d ",cur);
                s-=l;
                k--;
            }
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据