题解 P2879 【[USACO07JAN]区间统计Tallest Cow】

Teddy_Di · 2018-05-18 19:23:17 · 题解

大佬们的什么差分数组，线段树本蒟蒻其实都没学过嘤嘤嘤。。。 然后我的大概思路就是某巨佬老师讲的那样，先把所有牛的高度设为最高值，如果某两头牛之间能互相看到的话，那直接把中间所有牛都砍一刀（中间这些牛的高度都减一）然后最后输出就可以了。。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
struct node {
    int first;
    int second;
}h[10005];
int kdl[10005][10005];//这个用于去重
int n, f[10005], hest, r, t, a, b, c, d;//c，d貌似没用上。。
int main() {
    scanf("%d%d%d%d", &n, &t, &hest, &r);
    for (int i = 1; i <= n; i++) {
        f[i] = hest;
    }
    for (int i = 1; i <= r; i++) {
        scanf("%d%d", &a, &b);
        h[i].first = min(a, b);
        h[i].second = max(a, b);//让这二者中小的赋给first，大的赋给second
        if (kdl[a][b] == 1)continue;
        kdl[a][b] = 1;//如果已经算过一次就跳过，没算过就标记并运算
        for(int j=h[i].first+1;j<h[i].second;j++)f[j]--;
    }//把中间所有牛的高度减一
    for(int i=1;i<=n;i++)printf("%d\n",f[i]);
    return 0;
}