CodeForces-1305E Kuroni and the Score Distribution（构造）

传送门：CodeForces-1305E

思路分析

如果一开始从1，2，3这样递增排列，那么对于每一个$i$，它的贡献是$(i-1)/2$
如果最后一位加上2，那么它的贡献就会少1，所以先构造到数量大于等于$m$的排列
然后将最后一位加上$(sum-m)*2$,剩下没有构造的数从最后面开始，构造一个从$10^9$开始公差为最后一位+1的递减序列

样例输入

5 3

样例输出

4 5 9 13 18

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

int ans[N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m,i;
    cin>>n>>m;
    int sum=0;
    for(i=1;i<=n && sum<m;i++){
        sum+=(i-1)/2;
        ans[i]=i;
    }
    if(sum<m){
        cout<<-1<<endl;
        return 0;
    }
    if(sum>m){
        --i;
        ans[i]+=(sum-m)*2;
        ++i;
    }
    int ma=1e9;
    for(int j=n;j>=i;j--){
        ans[j]=ma;
        ma-=ans[i-1]+1;
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    




    return 0;
}