[Acwing] 4377. 农田灌溉 二分

前言

传送门 : 看了几篇题解,发现大佬的思路真是Orz

思路

首先一看这题就想到的是二分答案了, 将时间x作为时间进行二分

对于每一次 c h e c k check check暴力的遍历就行了

但是本来想优化一下 ,使用 s t [ ] st[] st[]数组将暴力 c h e c k check check的时候

i f ( s t [ i ] )   c o n t i n u e ; if(st[i])\ continue; if(st[i]) continue; 就是当前弄田如果被灌溉那么就不进行枚举

结果 W A WA WA了,百思不得其解,然后注释掉了,就 A C AC AC了，赛后也没多想

当然这题也有大佬使用 b i t s e t bitset bitset做的,我也只是Orz

Mycode

map mp;

const int N  = 210;
int a[N],n,k;
int b[N]; //因为每次都要check又要使用a[]进行浇水 所以多建立一个b[]

int st[N];

bool check(int x){


    for(int i=1;i=max(0,i-x+1);j -- ){
                b[j] = 1;
                // st[j] = 1;
            }

            for(int j=i;jn>>k;

    memset(a,0,sizeof a);

    for(int i=1;i>x;
        a[x] = 1;
    }


    int l = 0 , r = n ;

    while(l >1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    cout