题解 P6155 【修改】
kradcigam
2020-03-01 21:15:16
# 前言
其实我感觉这道题比第 $2$ 道题还略微的简单了一些。
# 正文
## 分析
### 性质
这道题,我们显而易见地可以得出一个结论,**最小化花费的情况下,改变的数,一定要尽量少。**
所以我们要先把数组排一遍序。
### 方法
这道题,我用了一个类似并查集的方法。
```cpp
int find(int x){
if(f[x]==0)return f[x]=x+1;
return f[x]=find(f[x]);
}
```
这里的 $f$ 数组就是表示以 $x$ 数组往后的最近的**可能**空位
## 总代码
会了以上 $2$ 个东西,我们就可以做这道题了。
```cpp
#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$,这个优化的效果还是很显著的。