题解：CF1967A Permutation Counting

yanqijin · 2024-08-07 07:29:02 · 题解

题目大意

给你一堆标号为 1 到 n 的卡牌，标号为 i 的卡牌有 a_i 张。你可以变出 k 张卡牌。你要最大化使用了 k 张卡牌之后排列出的连续的标号 1 到 n 的个数。

思路

一眼贪心。首先我们发现可以持续连着多少轮是由最小值决定的，所以我们考虑将最小值最大化。最大化最小值后再尽量放平均即可。

Code

#include<bits/stdc++.h>
using namespace std;
long long t,n,k,a[200005];
void read(long long &x)
{
    x=0;
    int w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
    x*=w;
}
void write(long long x)
{
    if(x<0) putchar('-'),x=-x;
    int sta[100];
    int top=0;
    do
    {
        sta[top++]=x%10,x/=10;
    }while(x);
    while(top) putchar(sta[--top]+48);
    putchar('\n');
}
int main()
{
    read(t);
    while(t--)
    {
        read(n);read(k);
        for(int i=1;i<=n;i++) read(a[i]);
        sort(a+1,a+1+n);//排序
        long long sum=0,id=0,gg=0;
        for(int i=1;i<=n;i++)
        {
            sum+=a[i];
            if(a[i]*i-sum<=k) id=i,gg=a[i]*i-sum;//最大化最小值
        }
        k-=gg;
        long long h=k/id,hh=k%id;
        long long f=a[id]+h;
        write(f*n-n+1+(n-id+hh));//平均
    }
    return 0;
}