题目链接

题意：

　　问满足一系列形如ab可以相互看到的约束的所有奶牛的最大身高（最高的编号和高度已给出）

分析：

　　首先，这个可以互相看到指的是中间的人比两头的都矮，一条斜线看到的不行，那么其实我们就可以直接默认每个牛都是最高的，然后有一个约束给中间的牛矮一些，最后找到处理后的数据就好了，数据处理方式：线段树or差分，当然这一题差分更快一些。

　　然后还有一个问题，就是他还要求b的身高大于等于a的，其实这个和没有一样，因为我们要求的是最大，能不变矮尽量不变，又因为如果有新的约束那么要不完全在a，b之内，要不完全在a，b之外（否则不可能），a，b就有同时改变了。

　　然后就是注意去一下重，即两个相同的约束不会使中间的身高改变2或以上（如果用这种方法计算最大）

　　最后就是代码。

#include <cstdio>

#include <algorithm>

#include <map>

using namespace std;

const int maxn=+;

int c[maxn];

map<pair<int,int>,bool> ma;

int main(){

    int n,s,h,m;

    scanf("%d%d%d%d",&n,&s,&h,&m);

    c[]=h;

    int js1,js2;

    for(int i=;i<=m;i++){

        scanf("%d%d",&js1,&js2);

        if(js1>js2)

            swap(js1,js2);

        if(ma[make_pair(js1,js2)])

            continue;

        c[js1+]--;

        c[js2]++;

        ma[make_pair(js1,js2)]=;

    }

    for(int i=;i<=n;i++){

        c[i]=c[i-]+c[i];

        printf("%d\n",c[i]);

    }

    return ;

}

巴特西

Tallest Cow，题解

题目链接

题意：

分析：

最新文章

热门文章