FZU Problem 2197 最小花费 简单贪心>

Problem 2197 最小花费

Accept: 210    Submit: 502

Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给一个长度为n（n <= 10^5）的“01”串，你可以任意交换一个为0的位和一个为1的位，若这两位相邻，花费为X，否则花费为Y。求通过若干次交换后将串中的“1”全部变换到“0”前面的最小花费。

Input

第一行一个整数T（1 <= T <= 10），表示测试数据的组数。接下来3*T行，每组数据三行，第一行为整数X（1 <= X <= 10^3），第二行为整数Y(X <= Y <= 10^3)，第三行是“01”串。

Output

最小花费。

Sample Input

2121100120011

Sample Output

03

Source

福州大学第十二届程序设计竞赛

思路：

我们每次取最后的1来替代最前面的0，然后选择策略时，取min{(i-j)*x，y},i,j分别代表1，0所在的位置，也就是说在一步步交换，和一次性交换中取

代价最小的就好了

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

const double eps=1e-8;
const double PI=acos(-1.0);
using namespace std;
char s[100005];
int a[100005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(s,0,sizeof(s));
        int x,y;
        scanf("%d %d",&x,&y);
        scanf("%s",s);
        int len=strlen(s);
        int ans=0;
        int mark=-1;
        for(int i=len-1; i>=0; i--)
        {
            if(s[i]=='1')
            {
                for(int j=mark+1; j<i; j++)
                {
                    if(s[j]=='0')
                    {
                        mark=j;//标记一下当前位置已经交换好了，下次就不用一直从0开始找了。
                        ans = min(ans + (i - j) * x, ans + y);
                        swap(s[i],s[j]);
                        break;
                    }
                }

            }
        }
        printf("%d\n",ans);
    }
    return 0;
}