题解 P3740 【[HAOI2014]贴海报】

不争不闹 · 2017-05-27 10:59:06 · 题解

数据范围虽大，实际数据却并没有多大。

纯暴力即可水过

不过我这个弄了个“二分”，只能说是比较怕纯暴力超时

正解可以用线段树，也可以用并查集

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define date 10000005
using namespace std;
int n,m;
int a,b;
int sum;
int ans;
int wall[date];
bool visited[1005];
int main()
{
//    freopen("ha14d.in","r",stdin);
//    freopen("ha14d.out","w",stdout);
    visited[0]=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        int mid=(a+b)>>1;
        for(int j=mid+1;j<=b,a<=mid;j++,a++,b--,mid--)
        {
            wall[j]=i;
            wall[b]=i;
            wall[mid]=i;
            wall[a]=i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!visited[wall[i]])
        {
            visited[wall[i]]=1;
            ans++;
        }
    }
    printf("%d",ans);
//    fclose(stdin);
//    fclose(stdout);
    return 0;
}