http://codeforces.com/contest/1313

B. Different Rules

 

题意:两场比赛,每场有个名次,最终名次为两场名次之和的排名,等于总名次小于等于自己的人数。问最多,最少多少名。

构造,贪心

由于同分都算自己前面,所以最多就是尽量凑和自己同分。最少就是尽量凑比自己多一分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int T;
int n, a, b;
int main() {
cin >> T;
while (T--) {
cin >> n >> a >> b;
int y = max(0, a + b - n);
cout << min(n, y + 1) << ' ' << min(n, a + b - 1) << endl;
}
return 0;
}

 

C2. Skyscrapers (hard version)

 

题意:给定n个位置的上限,要求每个数必须小于它的上限,且两边不能同时有比它大的数,要求总和最大。

看看样例也可以猜出来,就是一个单峰函数,就要枚举峰值的位置,同时要知道该点作为峰值时的最大值。

单调栈

分别处理出单调递增的递减时每个位置的最大值,枚举峰值时最大值就是左边递增+右边递减。

处理单调时递增如果比前一个大,直接就是前一个的值,否则不断删去单调栈里比当前大的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
int n;
ll a[N];
pii S[N]; int top;
ll d1[N], d2[N];
void solve(ll* d) {
top = 0;
for (int i = 1; i <= n; i++) {
d[i] = d[i - 1] + a[i];
int r = i;
if (a[i] < a[i - 1]) {
while (top&&S[top-1].first>=a[i]) {
d[i] -= 1ll * (r - S[top - 1].second)*(S[top - 1].first - a[i]);
r = S[--top].second;
}
}
S[top++] = pii(a[i], r);
}
}
ll tmp = -1; int ans = -1;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
solve(d1);
reverse(a + 1, a + n + 1);
solve(d2);
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
if (d1[i] + d2[1 + n - i]-a[i] > tmp) {
tmp = d1[i] + d2[1 + n - i] - a[i];
ans = i;
}
}
for (int i = ans - 1; i >= 1; i--) {
a[i] = min(a[i], a[i + 1]);
}
for (int i = ans + 1; i <= n; i++) {
a[i] = min(a[i], a[i - 1]);
}
for (int i = 1; i <= n; i++)printf("%lld%s", a[i], i == n ? "\n" : " ");
return 0;
}