[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;
}