Binary Transformations （贪心）Gym 101669F

发布时间：2020-12-15 08:01:09 所属栏目：Java 来源：网络整理

导读：分析：比较容易想到的是用两个容器分别存放需要‘1‘变为‘0‘的值以及需要‘0‘变为‘1‘的值，1-0需要从大到小排序，0-1的需要从小到大排序进行贪心选择但是如果存在这样的位置（变化前后都为1），我们就要枚举一开始把哪些这样的位置进行转换，显然是价

分析：比较容易想到的是用两个容器分别存放需要‘1‘变为‘0‘的值以及需要‘0‘变为‘1‘的值，1->0需要从大到小排序，0->1的需要从小到大排序进行贪心选择

但是如果存在这样的位置（变化前后都为1），我们就要枚举一开始把哪些这样的位置进行转换，显然是价值越大的越优先转换，因为这样代价小。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<set>
 6 #include<algorithm>
 7 using namespace std;
 8 const int maxn = 5010;
 9 #define LL long long
10 #define INF 0x3f3f3f3f
11 int n;
12 LL c[maxn],ans,sum;
13 char a[maxn],b[maxn];
14 vector<LL> V;
15 multiset<LL> tmp1,tmp2;
16 bool cmp(LL a,LL b){ return a>b; }
17 
18 LL cal(int x){
19     LL ans=0,ss=sum;
20     if(x) tmp1.insert(V[x-1]),tmp2.insert(V[x-1]);
21     multiset<LL>::iterator it2;
22     multiset<LL>::reverse_iterator it1;
23     for(it1=tmp1.rbegin();it1!=tmp1.rend();it1++){
24         ss-=(*it1);ans+=ss;
25     }
26     for(it2=tmp2.begin();it2!=tmp2.end();it2++){
27         ss+=(*it2);ans+=ss;
28     }
29     return ans;
30 }
31 
32 int main(){
33     scanf("%d",&n);
34     for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
35     scanf(" %s %s",a+1,b+1);
36     for(int i=1;i<=n;i++){
37         if(a[i]!=b[i]){
38             if(a[i]==‘1‘&&b[i]==‘0‘) tmp1.insert(c[i]);
39             else tmp2.insert(c[i]);
40         }
41         else if(a[i]==‘1‘&&b[i]==‘1‘){
42             V.push_back(c[i]);
43         }
44         if(a[i]==‘1‘) sum+=c[i];
45     }
46     sort(V.begin(),V.end(),cmp);
47     ans=(LL)(1e18);//注意这里不能是ans=INF;
48     for(int i=0;i<=V.size();i++){
49         ans=min(ans,cal(i));
50     }
51     printf("%lldn",ans);
52 
53     return 0;
54 }
55 
56 /*
57 5 5 2 6 1 5 01110 10011
58 */

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!