首页 > 电脑常识 > 区块链

牛客练习赛83 C.集合操作

admin 区块链 2021-05-25 09:26:26 思维 牛客练习赛 
后台-系统设置-扩展变量-手机广告位-内容正文底部

C.集合操作(思维,后缀)

题目传送门:

C.集合操作

题目:

在这里插入图片描述

思路:

数据量很大,操作数和每次减去的数<=1e18。那么如果模拟的话肯定妥妥的爆炸。我们比较容易可以想到如果很多个数在同一个p的区块时(这些数中的最大值和最小值的差小于p)那么将这里面的所有数同时减去p时,他们的相对大小是不变的。

那么我们就可以先把原来的数排个序,从后往前操作,将后面的数不断并到前面的区块上,当并到不能操作时再退出。剩下的操作再进行暴力模拟,剩下的操作数量必然小于n。所以时间复杂度为nlogn。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
LL n,k,d;
LL a[N];
LL cal(int x)   //分区
{
    if(x>=0) return x/d;
    return (x+1)/d-1;
}
int main()
{
    scanf("%lld%lld%lld",&n,&k,&d);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+1+n);    //从小到大排序
    if(d==0)
    {
        for(int i=1;i<=n;i++) printf("%lld ",a[i]);
        return 0;
    }
    int now=1;
    for(int i=n;i>=2;i--)
    {
        if(cal(a[i])==cal(a[i-1])) continue;
        LL p=cal(a[i])-cal(a[i-1]);
        LL q=n-i+1;
        LL sum=p*q;
        if(k>sum)
        {
            k=k-sum;
            continue;
        }
        now=i;
        break;
    }
    int f=k/(n-now+1);
    k=k%(n-now+1);
    for(int i=now+1;i<=n;i++)
    {
        LL p=cal(a[i])-cal(a[now]);
        a[i]=a[i]-p*d-f*d;
    }
    a[now]=a[now]-f*d;
    sort(a+1,a+1+n);
    for(int i=n;i>=n-k+1;i--)
        a[i]=a[i]-d;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) printf("%lld ",a[i]);
    system("pause");
    return 0;
}

文章来源:https://blog.csdn.net/Stevenwuxu/article/details/117196106

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://www.jcdi.cn/qukuailian/30800.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码