欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P2879 [USACO07JAN]Tallest Cow S

程序员文章站 2022-07-12 17:38:26
...

难度:4

初看觉得可能很难,但是不然,题目问的是每头牛可能的最大身高,只要满足题目里面的条件就行了,然后就是满足条件下的最大身高,然后思路就是设置一个数组,输入的牛是a和b,然后我就把a+1到b-1这个区间都减一,意思就是相比于两边的牛,至少矮了1,所以最后p位置最高处的牛一定为0,然后输出h+数组值,就得到了每头牛可能的最大身高,

然后可以优化的操作是对区间减1,有这样一个结论,对闭区间a到b,加上一个数,则a处加上x,b+1处减x,然后求前缀和即可,

然后就是本题的一个坑点,同样的一对关系可能被多次输入,需要判重,
这道题洛谷上面的数据太水了,就用了最朴素的算法也能过

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;

const int N = 10005;

int main() {
    int n, pos, h, m;
    cin >> n >> pos >> h >> m;
    int cnt[N] = {};
    map<pa, int> mp;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        if (mp.find(make_pair(a, b)) != mp.end()) continue;
        cnt[a + 1]--;
        cnt[b]++;
        /*for (int j = a + 1; j <= b - 1; j++) {
            cnt[j]--;
        }*/
        mp[make_pair(a, b)] = 1;
    }
    for (int i = 1; i <= n; i++) {
        cnt[i] += cnt[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        cout << cnt[i] + h << endl;
    }
    return 0;
}
相关标签: # 基本算法