题解 P6155 【修改】

# 前言 其实我感觉这道题比第 $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$，这个优化的效果还是很显著的。