CF D. Walking Between Houses (贪心）

题意：
现在有n个房子排成一列，编号为1~n，起初你在第1个房子里，现在你要进行k次移动，每次移动一都可以从一个房子i移动到另外一个其他的房子j里（i != j），移动的距离为|j - i|。问你进过k次移动后，移动的总和可以刚好是s吗？若可以则输出YES并依次输出每次到达的房子的编号，否则输出NO。

分析：首先观察下NO的情况，如果s<k 也就是说总步数都比不是次数的话，那肯定是NO拉，或者s>k*(n-1) 无论如何走都到吧了总步数，那也是NO;

什么时候是YES呢？我们可以贪心下，尽可能的走最大的，余下的步数肯定是小于（n-1），也就是每次走的路程是MIN（s-k,n-1); s-k就是用来解决余下的步数

#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{

    long long n,k,s;

    scanf("%lld%lld%lld",&n,&k,&s);

    if(s<k||k*(n-)<s)//最小与最大

    {

        puts("NO");

        return ;

    }

    puts("YES");

    int now=;

    while(k--)

    {

        int num=min(s-k,n-);

        s-=num;

        if(now+num<=n)

        now+=num;

        else

        now-=num;

        printf("%d ",now);

    }

    puts(" ");

    return ;

}

巴特西

CF D. Walking Between Houses (贪心）

最新文章

热门文章