luogu 1066 引水入城(bfs+贪心)

时间：2024-04-14 18:22:26

90分，有一个点TLE....

首先可以证明一个东西，如果从上面一排的某个点bfs一次到最下面一排的饮水点不是一个区间的话，那么最后一定所有饮水点不会被覆盖完的。

证明考虑反证法。

所以从上面一排的每个点bfs一次得到一个区间。题目转化为给出m个区间覆盖m个点的最小区间选择数。

显然是个明显的贪心，以左区间端点为第一关键字升序排序，右区间端点为第二关键字降序排序，那么每次贪心的选择一个覆盖最大的区间即可。

时间复杂度O(n*m^2+mlogm).需要常数优化。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int x=;char ch=getchar();

    while(ch<''||ch>''){ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int G[N][N], ps[][]={,,-,,,,,-};

bool vis[N][N], mark[N], flag=true;

struct Node{int l, r;}node[N];

queue<PII>que;

bool comp(Node a, Node b){

    if (a.l!=b.l) return a.l<b.l;

    return a.r>b.r;

}

int main ()

{

    int n, m, dx, dy;

    PII tmp;

    n=Scan(); m=Scan();

    FOR(i,,n) FOR(j,,m) G[i][j]=Scan();

    FOR(i,,m) {

        mem(vis,false);

        que.push(mp(,i)); vis[][i]=true;

        while (!que.empty()) {

            tmp=que.front(); que.pop();

            FO(j,,) {

                dx=tmp.first+ps[j][], dy=tmp.second+ps[j][];

                if (dx<||dy<||dx>n||dy>m||vis[dx][dy]||G[tmp.first][tmp.second]<=G[dx][dy]) continue;

                vis[dx][dy]=true; que.push(mp(dx,dy));

            }

        }

        FOR(j,,m) {

            if (vis[n][j]) {

                mark[j]=true;

                if (flag) {

                    if (!vis[n][j-]) {

                        if (node[i].l) flag=false;

                        else node[i].l=j;

                    }

                    if (!vis[n][j+]) node[i].r=j;

                }

            }

        }

    }

    int ans=;

    FOR(i,,m) if (!mark[i]) ++ans;

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

    else {

        sort(node+,node+m+,comp);

        int now=;

        while (node[now].r==) ++now;

        int ma=node[now].r, r; ++now; ++ans;

        while (now<=m) {

            r=ma;

            if (r==m) break;

            while (now<=m&&node[now].l<=r+) ma=max(ma,node[now].r), ++now;

            ++ans;

        }

        printf("1\n%d\n",ans);

    }

    return ;

}

相关文章