arc079

D. Decrease (Contestant ver.)

大意: 每次操作选一个最大数$-n$,其余数全$+1$. 要求构造一个序列$a$, 使得恰好$k$次操作后最大值不超过$n-1$.

只要让$k$次操作以后恰好变全为$n-1$即可.

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)

#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

ll a[];

int main() {

    ll k;

    cin>>k;

    ll p = k/, r = k-*p;

    int n = ;

    REP(i,,n) a[i] = p+;

    REP(i,,r) a[i]+=n-r+;

    REP(i,r+,n) a[i]-=r;

    printf("%d\n",n);

    REP(i,,n) printf("%lld ",a[i]);hr;

}

E. Decrease (Judge ver.)

大意: 给定序列$a$, 求进行多少次$D$题中的操作后, 最大值不超过$n-1$.

暴力模拟

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)

#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

#ifdef __APPLE__

const int N = 1e2+;

#else

const int N = 1e6+;

#endif

int n;

ll a[N];

int calc() {

    int ans = ;

    while () {

        sort(a+,a++n);

        if (a[n]<=n-) break;

        ++ans;

        a[n]-=n;

        REP(i,,n-) ++a[i];

    }

    return ans;

}

int main() {

    scanf("%d", &n);

    REP(i,,n) scanf("%lld",a+i);

    ll ans = ;

    while () {

        sort(a+,a++n);

        if (a[]>) {

            ll t = a[]-;

            ans += t*n;

            REP(i,,n) a[i]-=t;

        }

        if (a[n]<=) {

            ans += calc();

            break;

        }

        ll ma = -;

        int p = ;

        REP(i,,n) if (a[i]-a[i-]>ma) ma = a[i]-a[i-], p = i;

        if (ma<=) throw;

        ll w = n-p+, t = (a[p]-a[p-])/(n+);

        ans += t*w;

        REP(i,,p-) a[i] += t*w;

        REP(i,p,n) a[i] += t*(-n+w-);

    }

    printf("%lld\n", ans);

}

巴特西

arc079

最新文章

热门文章