程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved