# luogu P6155 修改题解()-其他

## luogu P6155 修改题解()

### code

``````//#pragma GCC optimize(2)
#include <iostream>
#define ull unsigned long long
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;
const int maxN= 1e6+10;
int b[maxN],cost[maxN],n,temp,idx;
vector<int> a;
ull ans=0;
unordered_map<int,int> mp;
priority_queue<int,vector<int>,less<int> >q;

bool comp(int x,int y){
return x>y;
}

signed main(){
//freopen("test.in","r",stdin);
ios::sync_with_stdio(false);//cin加速
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);//再度加速
//不能用printf,scanf
cin >> n ;
for(int i=1;i<=n;++i)
cin >> temp,a.push_back(temp), mp[temp]++;
for(int i=1;i<=n;++i)
cin >> b[i];
a.push_back(0x7ffffff);
sort(a.begin(),a.end());
//	for(int x:a){
//		cout << x << ' ';
//	}cout << endl;
int n=unique(a.begin(),a.end())-a.begin(),maxn=0;
//a[n+1]=0x7ffffff;
//	cout << n << endl;
for(int i=0;i<n-1;++i){
maxn=max(maxn,a[i]);
mp[a[i]]--;
cost[++idx]=0;
int p=1;
while(mp[a[i]]&&(a[i]+p<a[i+1])){
cost[++idx]=p;
maxn=max(maxn,a[i]+p);
++p,--mp[a[i]];
}
if(mp[a[i]]){
while(mp[a[i]]--) q.push(a[i]);
}
else{
while(a[i]+p<a[i+1]&&!q.empty()){
cost[++idx]=a[i]+p-q.top();
q.pop();
p++;
}
}

//	cout << cost[i] << endl;
}
//cout << idx << endl;
//cout << maxn <<
sort(cost+1,cost+idx+1);
sort(b+1,b+idx+1,comp);
//for(int i=1;i<=idx;++i)
//	cout << cost[i] << " ";
//cout << endl;
for(int i=1;i<=idx;++i)
ans+=(ull)b[i]*(ull)cost[i];
cout << ans << '\n';

return 114514-114514;
}

``````
————————

### code

``````//#pragma GCC optimize(2)
#include <iostream>
#define ull unsigned long long
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;
const int maxN= 1e6+10;
int b[maxN],cost[maxN],n,temp,idx;
vector<int> a;
ull ans=0;
unordered_map<int,int> mp;
priority_queue<int,vector<int>,less<int> >q;

bool comp(int x,int y){
return x>y;
}

signed main(){
//freopen("test.in","r",stdin);
ios::sync_with_stdio(false);//cin加速
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);//再度加速
//不能用printf,scanf
cin >> n ;
for(int i=1;i<=n;++i)
cin >> temp,a.push_back(temp), mp[temp]++;
for(int i=1;i<=n;++i)
cin >> b[i];
a.push_back(0x7ffffff);
sort(a.begin(),a.end());
//	for(int x:a){
//		cout << x << ' ';
//	}cout << endl;
int n=unique(a.begin(),a.end())-a.begin(),maxn=0;
//a[n+1]=0x7ffffff;
//	cout << n << endl;
for(int i=0;i<n-1;++i){
maxn=max(maxn,a[i]);
mp[a[i]]--;
cost[++idx]=0;
int p=1;
while(mp[a[i]]&&(a[i]+p<a[i+1])){
cost[++idx]=p;
maxn=max(maxn,a[i]+p);
++p,--mp[a[i]];
}
if(mp[a[i]]){
while(mp[a[i]]--) q.push(a[i]);
}
else{
while(a[i]+p<a[i+1]&&!q.empty()){
cost[++idx]=a[i]+p-q.top();
q.pop();
p++;
}
}

//	cout << cost[i] << endl;
}
//cout << idx << endl;
//cout << maxn <<
sort(cost+1,cost+idx+1);
sort(b+1,b+idx+1,comp);
//for(int i=1;i<=idx;++i)
//	cout << cost[i] << " ";
//cout << endl;
for(int i=1;i<=idx;++i)
ans+=(ull)b[i]*(ull)cost[i];
cout << ans << '\n';

return 114514-114514;
}

``````