欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #681 B. Saving the City(贪心)

程序员文章站 2022-06-02 22:16:46
...

Codeforces Round #681 B. Saving the City(贪心)

题意:
T组样例,点燃一个地雷 i i i时相邻的地雷 ( i − 1 , i + 1 ) (i-1,i+1) (i1,i+1)都会爆炸,点燃一个地雷需要a个点数,放置一个地雷需要b个点数,现在需要炸掉给的s中所有的1,最小化花费的点数
题解:
贪心,注意边界条件
code:

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
 
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define pb push_back
#define all(a) a+1,a+n+1
#define ALL(a) a.begin(),a.end()
#define debug(a) cout <<#a << "=" << a << endl;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll<<60;
const int mod=1e9+7;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
 //上面是模板,与解题无关-----------------------------------------------
int main(){
    int t;cin>>t;
    while(t--){
        int a,b;
        string s;
        cin>>a>>b>>s;
        int len=s.size(),cnt=50000,pos=len+100;
        rep(i,0,len-1){//找到第一个1所在位置
            if(s[i]=='1') {
                pos=i;break;
            }
        }
        ll ans=0,f=0;//f判断本段是否已经引爆
        rep(i,pos,len-1){
            if(s[i]=='1'){
                if(!f){
                    ans+=min(a,cnt*b);//注意此处的更新条件
                    f=1;
                    cnt=0;
                }
            }
            else{
                f=0;
                cnt++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}```

相关标签: codeforces