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;
}
推荐阅读
-
P2879 [USACO07JAN]区间统计Tallest Cow
-
[洛谷]P2879 [USACO07JAN]区间统计Tallest Cow (#模拟)
-
差分+思维 [USACO07JAN]Tallest Cow S(洛谷 P2879)
-
差分数组-P2879 [USACO07JAN]区间统计Tallest Cow
-
[USACO07JAN]区间统计Tallest Cow
-
题解 P2879 【[USACO07JAN]区间统计Tallest Cow】
-
P2879 [USACO07JAN]Tallest Cow S
-
洛谷 P2879 [USACO07JAN]区间统计Tallest Cow
-
P2879 [USACO07JAN]Tallest Cow S
-
P2879 [USACO07JAN]Tallest Cow S