题解 P2207 【Photo】

呆瓜yy · 2019-03-16 10:05:06 · 题解

一篇很水的题解

首先，观察题目可知，既然N很大，K很小（假装是吧），那么突破口就在于K

假设一下，如果知道从哪里把奶牛分开，题目就很简单了，但如果用for循环n硬做，肯定会超时的。于是，根据科学猜题法，要做的是for循环k来找断点

以下是很水的时间为ans*k的算法：

首先从1-n枚举第i头奶牛（会优化的，理论上不会超时），作为第ans张照片的第一头奶牛

然后在k个限制中找到a>=i对应的最小b值（当然，这需要排序）

最后ans++，i直接跳到找到的b

关于这个方法的解释：

如果我们要确定一张照片的奶牛，则必须保证这张照片中的奶牛关系友好。换句话说，就是找到第一只与照片中的奶牛关系不好的奶牛的前一只作为这张照片的最后一只奶牛。

于是我们可以枚举第一头奶牛i，并在k个限制中寻找第一只不能存在于同一照片中的奶牛（注意：若当前的a<i，则对应的b对于这张照片无影响）

很水的代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
namespace lyy
{
    int n,k,j,i,yy,ans;
    const int INF=0x7f7f7f7f;
    struct photo
    {
        int a,b;
    }p[1005];
}
using lyy::n;//忽略这些细节，只是为了好玩
using lyy::k;
using lyy::p;
using lyy::i;
using lyy::j;
using lyy::yy;
using lyy::ans;
using lyy::INF;
bool cmp(lyy::photo x,lyy::photo y)
{
    if(x.a!=x.b)
      return x.a<y.a;
    return x.b<y.b;
}
int main()
{
//  freopen("photo.in","r",stdin);
//  freopen("photo.out","w",stdout);
    cin>>n>>k;
    for(i=1;i<=k;i++)
    {
        cin>>p[i].a>>p[i].b;
        if(p[i].a>p[i].b)
          swap(p[i].a,p[i].b);
    }
    sort(p+1,p+k+1,cmp);
    for(i=1;i<=n;)
    {
        yy=INF;
        for(j=1;j<=k;j++)
          if(p[j].a>=i)
            yy=min(yy,p[j].b);
        ans++;
        i=yy;
    }
    cout<<ans;
    return 0;
}