题解 P6155 【修改】

2020-03-01 21:15:16


前言

其实我感觉这道题比第 $2$ 道题还略微的简单了一些。

正文

分析

性质

这道题,我们显而易见地可以得出一个结论,最小化花费的情况下,改变的数,一定要尽量少。

所以我们要先把数组排一遍序。

方法

这道题,我用了一个类似并查集的方法。

int find(int x){
    if(f[x]==0)return f[x]=x+1;
    return f[x]=find(f[x]);
}

这里的 $f$ 数组就是表示以 $x$ 数组往后的最近的可能空位

总代码

会了以上 $2$ 个东西,我们就可以做这道题了。

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &FF){
    T RR=1;FF=0;char CH=getchar();
    for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
    for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
    FF*=RR;
}
template<typename T>void write(T x){
    if(x<0)putchar('-'),x*=-1;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
const int MAXN=1e6;
int a[MAXN];
unsigned long long b[MAXN],ans,n;
unordered_map<int,int>f;
int find(int x){
    if(f[x]==0)return f[x]=x+1;
    return f[x]=find(f[x]);
}
vector<int>v;
bool cmp(int a,int b){
    return a>b;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++)read(a[i]);//读入a数组
    sort(a+1,a+n+1,cmp);//排序
    for(int i=1;i<=n;i++){
        int x=find(a[i])-a[i]-1;//当然是要减1的
        if(x)v.push_back(x);//插入
    }
    for(int i=1;i<=n;i++)read(b[i]);
    sort(b+1,b+n+1);//排序b数组,显然
    sort(v.begin(),v.end());
    for(int i=v.size()-1,j=1;i>=0;i--,j++)ans+=v[i]*b[j];//算和
    write(ans);//输出
    return 0;
}

后记

这道题,我程序运行的时间想对还是比较慢的,但是这种是可以过的。

欢迎在评论区指出错误,也欢迎优化此算法。

感谢 @北辰yama 和 @天下我有 的提醒,本算法已经从原来的 $9.42s$ 变成了 $5.70s$ ,这个优化的效果还是很显著的。