bzoj 3119: Book

Description

Wayne喜欢看书，更喜欢买书。
某天Wayne在当当网上买书，买了很多很多书。Wayne有一个奇怪的癖好，就是第一本书的价格必须恰为X，而之后买的每一本书，若是比上一本更昂贵，则价格最多多A元；若是比上一本更便宜，则价格最多少B元。
Wayne心血来潮，一口气买了N本书，但他记不得每本书的价格了，只记得总价格是M。Wayne于是很想知道一种可能的书价分布。为了简化问题，我们假定书价的定义域是整数，且每本书与上一本书的价格差，要么恰为+A，要么恰为-B。
只要给出任意一个合法的书价序列就算正确。

Input

第一行一个正整数N。
第二行四个整数依次是X,A,B,M。

Output

输出一行N个整数，用空格隔开。数据保证有解。

先全部+A，计算还差(A+B)的多少倍，位置x减去(A+B)对总和的影响是n-1-x，贪心选影响大的位置即可。

#include<cstdio>
typedef long long i64;
int n,a,b;
i64 m,z,x;
int main(){
    scanf("%d%lld%d%d%lld",&n,&x,&a,&b,&m);
    b+=a;
    z=(n*x+i64(a)*n*(n-1)/2-m)/b;
    for(int i=n-1;i;--i){
        printf("%lld ",x);
        x+=a;
        if(z>=i)z-=i,x-=b;
    }
    printf("%lld",x);
    return 0;
}