#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+7;
string S,T;
int n,a[N],cnt,seq[N];
priority_queue<int> pay1;
priority_queue<int,vector<int>,greater<int> > pay2;
vector<int> down,up,dsum,usum;
int sum,ans;
void dbg(){
cout<<"size: "<<down.size()<<" "<<up.size()<<endl;
for(int i=0;i<down.size();i++){
cout<<down[i]<<" ";
}
cout<<endl;
for(int i=0;i<up.size();i++){
cout<<up[i]<<" ";
}
cout<<endl;
}
void solve(){
for(int i=1;i<=cnt;i++){
int pos1=lower_bound(down.begin(),down.end(),seq[i])-down.begin();
int pos2=lower_bound(up.begin(),up.end(),seq[i])-up.begin();
int cbt=((down.size()-pos1+1)+(up.size()-pos2))*seq[i];
cbt+=dsum[pos1-1]+usum[pos2-1];
if(cbt<seq[i]*(down.size()+up.size())){
down.insert(lower_bound(down.begin(),down.end(),seq[i]),seq[i]);
up.insert(lower_bound(up.begin(),up.end(),seq[i]),seq[i]);
ans+=cbt;
}
else ans+=seq[i]*(down.size()+up.size());
}
}
signed main(){
//freopen("key.in","r",stdin);
//freopen("key.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>S>>T;
for(int i=0;i<n;i++){
if(S[i]=='1'&&T[i]!='1') sum+=a[i+1];
if(S[i]=='1'&&T[i]=='1') seq[++cnt]=a[i+1];
if(S[i]=='1'&&T[i]=='0') pay1.push(a[i+1]);
else if(S[i]=='0'&&T[i]=='1') pay2.push(a[i+1]);
}
//cout<<sum<<endl;
while(pay1.size()){
dsum.push_back(sum);
ans+=(sum-=pay1.top());
down.push_back(pay1.top());
pay1.pop();
//cerr<<sum<<endl;
}
while(pay2.size()){
ans+=(sum+=pay2.top());
up.push_back(pay2.top()) ;usum.push_back(sum);
pay2.pop();
}
sort(seq+1,seq+cnt+1,greater<int>());
sort(down.begin(),down.end());
sort(dsum.begin(),dsum.end());
sort(up.begin(),up.end());
sort(usum.begin(),usum.end());
solve();
cout<<ans;
return 0;
}
大样例过了，我已经不想再调了呜呜
1 个赞
#include<bits/stdc++.h>
using namespace std;
long long n,kms,kj=0;
struct p{
long long c;
char a,b;
}c[5005];
bool cmp(p x,p y){
return x.c>y.c;
}
set<long long,greater<long long> >s;
set<long long>k;
signed main(){
freopen("key.in","r",stdin);
freopen("key.out","w",stdout);
cin>>n;
for(long long i=1;i<=n;i++)cin>>c[i].c;
for(long long i=1;i<=n;i++)cin>>c[i].a;
for(long long i=1;i<=n;i++)cin>>c[i].b;
sort(c+1,c+n+1,cmp);
for(long long i=1;i<=n;i++){
if(c[i].a!=c[i].b){
if(c[i].a=='0')k.insert(c[i].c);
else s.insert(c[i].c),kj+=c[i].c;
}
}
for(long long i=1;i<=n;i++){
if(c[i].a==c[i].b&&c[i].a=='1'){
kms+=c[i].c;
}
}
long long sum=1e18,ans=0;
long long kk=(kj),ll=(kms);
for(auto j:s){
kk-=j;
ans+=kk;
ans+=ll;
}
for(auto j:k){
kk+=j;
ans+=ll;
ans+=kk;
}
sum=min(sum,ans);
for(long long i=1;i<=n;i++){
if(c[i].a==c[i].b&&c[i].b=='1'){
ans=0;
long long kk=(kj+=c[i].c),ll=(kms-=c[i].c);
s.insert(c[i].c);
for(auto j:s){
kk-=j;
ans+=kk;
ans+=ll;
}
k.insert(c[i].c);
for(auto j:k){
kk+=j;
ans+=ll;
ans+=kk;
}
sum=min(sum,ans);
}
}
cout<<sum;
}
```60分完整代码
#include<bits/stdc++.h>
using namespace std;
long long n,kms,kj=0;
struct p{
long long c;
char a,b;
}c[5005];
bool cmp(p x,p y){
if(x.c!=y.c)return x.c>y.c;
return x.a>y.a;
}
set<long long,greater<long long> >s;
set<long long>k;
map<long long,int>S,K;
//k从小到大代价，s从大到小代价,K,S记录个数（set会去重）
signed main(){
freopen("key.in","r",stdin);
freopen("key.out","w",stdout);
cin>>n;
for(long long i=1;i<=n;i++)cin>>c[i].c;
for(long long i=1;i<=n;i++)cin>>c[i].a;
for(long long i=1;i<=n;i++)cin>>c[i].b;
sort(c+1,c+n+1,cmp);//排序
for(long long i=1;i<=n;i++){
if(c[i].a!=c[i].b){
if(c[i].a=='0')K[c[i].c]++,k.insert(c[i].c);
else s.insert(c[i].c),S[c[i].c]++,kj+=c[i].c;//kj(1->0总和)
}
}
for(long long i=1;i<=n;i++){
if(c[i].a==c[i].b&&c[i].a=='1'){
kms+=c[i].c;//前缀和（总和1->0->1代价）
}
}
long long sum=1e18,ans=0;
long long kk=(kj),ll=(kms);//临时变量
//1->1不动代价
for(auto j:s){
// cout<<j<<" ";
for(int i=1;i<=S[j];i++){//有S[j]个
kk-=j;//总和减少
ans+=kk;
ans+=ll;//加上本来是一不动的
}
}
// cout<<kk<<" ";
for(auto j:k){
for(int i=1;i<=K[j];i++){//有K[j]个
kk+=j;
ans+=ll;
ans+=kk;//加上本来是一不动的
}
}
sum=min(sum,ans);//取最小
for(long long i=1;i<=n;i++){
if(c[i].a==c[i].b&&c[i].b=='1'){
ans=0;//清零
long long kk=(kj+=c[i].c),ll=(kms-=c[i].c);//kk:1->0增加总和,ll:加上本来是一不动的
s.insert(c[i].c);//插入
S[c[i].c]++;
for(auto j:s){
for(int jk=1;jk<=S[j];jk++){
kk-=j;
ans+=kk;
ans+=ll;
}
}
// kk=0;
// cout<<kk<<" ";
k.insert(c[i].c);
K[c[i].c]++;
for(auto j:k){
for(int jk=1;jk<=K[j];jk++){
kk+=j;
ans+=ll;
ans+=kk;
}
}
sum=min(sum,ans);
}
}
cout<<sum;
}
看懂了吗？
我还是自己重构吧
也是重构了还发了篇题解，就30多行代码
1 个赞