Dark`Kris

Private blog

I'm spark , hope you fire


NOIp2010TG/Luogu P1514 引水入城 解题报告

现在开始在博客上写解题报告也是有点晚了,毕竟还有5天就是高三狗了,距离NOIp2016只有77天。博主在NOIp2015的表现十分不令人满意,于是想再最后搏一次,希望能拿上一等奖,也算是给自己的努力一个证明。 写这个解题报告一是整理自己的思路,希望让自己不要忘了这道题;二是做个记录,感觉引水入城这道题很经典,等到赛前复习的时候可以拿来看看,快速复习。

下面来看一下题目

题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。 引水入城 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此,只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。由于第N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

输入输出格式:

输入格式: 输入文件的每行中两个数之间用一个空格隔开。输入的第一行是两个正整数N 和M,表示矩形的规模。接下来N 行,每行M 个正整数,依次代表每座城市的海拔高度。
输出格式: 输出有两行。如果能满足要求,输出的第一行是整数1,第二行是一个整数,代表最少建造几个蓄水厂;如果不能满足要求,输出的第一行是整数0,第二行是一个整数,代表有几座干旱区中的城市不可能建有水利设施。

输入输出样例:

【输入样例1】 2 5 9 1 5 4 3 8 7 6 1 2

【输入样例2】 3 6 8 4 5 6 4 4 7 3 4 3 3 3 3 2 2 1 1 2

【输出样例1】 1 1

【输出样例2】 1 3

说明: 【样例1 说明】 只需要在海拔为9 的那座城市中建造蓄水厂,即可满足要求。 【样例2 说明】 引水入城 上图中,在3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这3 个蓄水厂为源头

在干旱区中建造的输水站分别用3 种颜色标出。当然,建造方法可能不唯一。

【数据范围】 数据范围


解题思路

DFS/BFS+贪心 Ps.感谢Clove_unique的博文启发了我,同时也学习了一下其解题思路及优化。

先从第一行开始每一格为起点搜索一次,边扫边置标志,搜索完成后最后一行会生成几条线段,将其记录下来。(其实可以径行优化,只有$h_{i,1}>=h_{i+1,1} , h_{i-1,1} $时才以这个格子开始进行搜索,这让可以避免重复搜索)[h数组记录当前格点的高度] 等完成这个工作,判断一下最后一行每个格子是否已经置标志了,如果不是就cnt++,最后输出0和cnt就可以了。 如果每个格子已经置标志,那么这道题就变成了区间覆盖问题(详见刘汝佳粉书贪心法第一讲),我们之前搜索时记录下的线段就派上了用场。 我们将线段按左端点从小到大排列(主关键字),右端点从大到小排列(次关键字)。排完后,第一个线段是一定要留下的,它覆盖的区域我们成为:灰色区域{i,j}。然后我们从第二个线段开始,查找左端点在{i,j+1}之内且右端点最大的线段留下来,此时答案加一。全部扫完之后输出1和答案就完成这道题目了。

下面是代码:(80分程序,两个点TLE,因为没写出来AC程序)

//P1514
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int MAXN=505,MAXM=505,INF=0xffffff;
const int dx[5]={0,0,1,0,-1},dy[5]={0,-1,0,1,0};
int n,m,h[MAXN][MAXM],linenum,ans,cnt;//x=m,y=n
bool flag[MAXN],flag1[MAXN],fflag;
struct node
{
    int left,right;
}line[MAXN];

void dfs(int x,int y)
{
    if(y==n)
    {
        flag[x]=true;
        flag1[x]=true;
    };
    for(int k=1;k<=4;k++)
    {
        if(h[x][y]>h[x+dx[k]][y+dy[k]])
        {
            dfs(x+dx[k],y+dy[k]);
        };
    };
}

bool compare(node a,node b)
{
    if(a.left<b.left)return true;else
        if(a.left==b.left&&a.right>b.right)return true;
    return false;
};

void work(int i)
{
    dfs(i,1);
    //for(int j=1;j<=m;j++)
    //   cout<<flag[j];
    //cout<<endl;
    int st=0,en=0;
    for(int j=1;j<=m+1;j++)
    {
        if(st==0&&flag1[j])st=j;
           if(!flag1[j]&&flag1[j-1])
           {
               en=j-1;
               line[++linenum].left=st;
              line[linenum].right=en;
              st=0; en=0;
         };
    }
}

int main()
{
    cin>>n>>m;
    //for(int i=1;i<=n;i++)line[i].left=line[i].right=0;
    //for(int i=1;i<=n;i++)flag[i]=false;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>h[j][i];
    for(int i=1;i<=m;i++)
    {
        h[i][0]=INF;
        h[i][n+1]=INF;
    };
    for(int i=1;i<=n;i++)
    {
        h[0][i]=INF;
        h[m+1][i]=INF;
    };
    fflag=true;

    for(int i=1;i<=m;i++)
    {
        memset(flag1,0,sizeof(flag1));
        if(i==1)work(i);else
            if(i==m)work(i);else
                if(h[i][1]>=h[i+1][i]&&h[i][1]>=h[i-1][1]) work(i);
    };

    //for(int i=1;i<=m;i++)cout<<flag[i]<<" ";
    //cout<<endl;

    for(int i=1;i<=m;i++)
    {
        if(!flag[i])
        {
            fflag=false;
            cnt++;
        };
    };
    if(fflag)
    {
        sort(line+1,line+linenum+1,compare);

        //for(int i=1;i<=linenum;i++)cout<<line[i].left<<" "<<line[i].right<<endl;
        int last=2;
        int nowRight(line[1].right);
        ans=1;
        while(nowRight!=m)
        {
            int maxr(nowRight);
            for(int i=last;i<=linenum;i++)
            {
                if(line[i].left<=nowRight+1&&maxr<line[i].right)maxr=line[i].right;
                if(line[i].left>nowRight+1){last=i;break;};
            };//更新last,这个优化时因为线段已经排好序,所以前面的不用扫了
            ans++;
            nowRight=maxr;
        };
        cout<<1<<endl<<ans;
    }else
    {
        cout<<0<<endl<<cnt;
    };
    return 0;
}

感谢惠读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading