程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> FZU 2041 Checker （貪心+模擬）

FZU 2041 Checker （貪心+模擬）

編輯：C++入門知識

FZU 2041 Checker （貪心+模擬）

這個題是昨天的隊內選拔賽用的套題裡的其中一道題，我當時想到方法了，但是沒敢寫。。一個是對復雜度有些不確定，萬一組數很多的話好像就會跪。。而且感覺不太好實現，隊裡還卡著兩道題，就打算等別的該出的題出了之後再寫，結果沒時間了。。
剛才按照那思路寫了一下。。結果就過了。。。真心醉了。。我&……%￥%**……%%
思路是先枚舉每個空隙，然後對該空隙向左向右貪心的一步步的去移動，剩下的就是小模擬了。然後找出所有空隙可能擴大的最大值就可以了。
代碼如下：

#include 
#include 
#include 
#include 
#include
#include 
#include 
#define LL __int64
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define eqs 1e-15
const int mod = 1e9+7 ;
using namespace std ;
char s[600];
int a[600], cnt;
struct node {
        int l, r, x;
} fei[600];
int main()
{
        int t, n, m, i, j, flag, lstep, rstep, max1, step, Case=0, mm;
        scanf(%d,&t);
        while(t--) {
                scanf(%d%d,&n,&mm);
                scanf(%s,s+1);
                s[0]='1';
                s[n+1]='1';
                cnt=0;
                flag=0;
                max1=0;
                for(i=0; i<=n+1; i++) {
                        if(s[i]=='1') {
                                if(flag) {
                                        flag=0;
                                        fei[cnt].r=i;
                                        cnt++;
                                }
                                fei[cnt].l=i;
                                fei[cnt].x=0;
                        } else {
                                flag=1;
                                fei[cnt].x++;
                                max1=max(max1,fei[cnt].x);
                        }
                }
                for(i=0; i=0; j--) {
                                        if(!a[j]) {
                                                lstep=fei[i].l-j;
                                                break;
                                        }
                                }
                                rstep=INF;
                                for(j=fei[i].r; j<=n+1; j++) {
                                        if(!a[j]) {
                                                rstep=j-fei[i].r;
                                                break;
                                        }
                                }
                                step=min(lstep,rstep);
                                if(m