Convert to Ones CodeForces（超水题）

题目大意：给你几个数，这些数里面只有0或1，你有两种操作：1.把一段区域内的所有数前后交换位置。2.把一段区域内所有数取反。（区域可大可小，可以是所有数也　可以只有一个数）。两个操作各有它的代价，你操作一次就要消耗一次代价，求把所有数都变成1所需要的最小代价。

输入：第一行输入n , ab, c ：表示有n个数，操作1代价b，操作2代价c；

　　第二行输入n个数，就是你要操作的数组。

输出：一行，输出最小代价。

题目分析：

1.如何运用操作1 ：

我们可以通过操作1把所有的0聚到同一个区域内，再用操作2“一杆收”。

2.如何进行比较：

①需要几次操作：原来一共有n组0。（就是几个0处于同一个区域算作一个“组”），我们可以发现：每个1操作最多会使两个“0组”合并。（一次操作 1一定可以把两个不连通的“0组”变成一个大的“0组”，可以自己摸拟试试，确实是这样）每个2操作最多能消灭一个“0组”。所以我们一共需要n次操作，因为每种操作都相当于把“0组”的个数减少了1。

②操作1最多用几次：我们需要n-1次操作1把所有0聚在一起。然后我们需要1次操作2来把一组0给转化。此时操作1使用次数最多，代价 b*（n-1）+c。

③操作2最多用几次：把所有的“0组”全部转化即可，代价c*n。

　　我们会发现，两者都是用了n次操作，所以c和b哪个小哪个多用就可以保证最终代价变小，所以最后结果就是min（b*（n-1）+c , c*n）。换言之：c和b有大小之分，而且一共使用的次数是一定的，那么肯定让代价少的操作尽可能多使用。

上代码！

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=3e5+10;//数据范围

int a[maxn];char s[maxn];

int n,b,c;

long long cnt;

int main(){

        scanf("%d %d %d",&n,&b,&c);

        scanf("%s",s);//输入是连着的数字，用一个字符串存

        int i=0;

        while(s[i]!='\0'){

            a[i+1]=s[i]-'0';

            i++;

        }//把字符串转为整形数组

        for(int i=1;i<=n;i++){

            if(a[i]==0){

                while(a[i]==0){

                    i++;

                }//跳出循环时候，一个“0组”被遍历完毕。

                cnt++;

            }

        }

        //cnt表示有几个“0组”

        if(cnt==0){

            printf("0\n");

            return 0;

        }//如果这里不特判，（cnt-1）*b+c可能为负，结果就错了

        printf("%lld\n",1ll*min(cnt*c,(cnt-1)*b+c));//cnt,b,c<3e6,cnt*c可能超过int范围 


    return 0;

}

巴特西

Convert to Ones CodeForces（超水题）

最新文章

热门文章