手速慢了,掉分
C. Another Permutation Problem
题意
给定一个正整数\(n\),设序列\(p\)为\(n\)的排列,求\(\sum_{i=1}^{n}p_i \times i-max_{j=1}^np_j\times j\)的最大值。
思路
打表可知,答案的排列一定为翻转一部分后缀。暴力枚举要翻转的后缀即可。
代码
void solve() {
int n;
cin >> n;
int ans = 0;
for(int i = 1; i < n; i++) {
ans += i * i;
}
for(int i = 0; i < n; i++) {
int x = 0, y = 0, mx = 0;
for(int j = 1; j <= i; j++) {
x += j * j;
mx = max(mx, j * j);
}
for(int j = n, k = i + 1; j > i; j--, k++) {
y += k * j;
mx = max(mx, k * j);
}
ans = max(ans, x + y - mx);
}
cout << ans << "\n";
}
D. Andrey and Escape from Capygrad
题意
给定一些包含区间,\([l, r]\)包含区间\([a,b]\),如果一个人在区间\([l,r]\)内,那么他可以传送到区间\([a,b]\)中的任意点。现给定一些坐标,求从该总表出发,最大能传送到的坐标在哪里。
思路
题意可简化为有若干个区间\([l,b]\),在区间\([l,b]\)内可传送到端点\(b\),求最大能传送到的坐标。
先合并重合的区间,再对于每个询问的坐标,二分找到所在的区间。若该坐标不在任何区间,则答案为它自已。
代码
void solve() {
int n;
cin >> n;
vector<array<int, 2>> seg(n);
for(int i = 0; i < n; i++) {
int l, r, a, b;
cin >> l >> r >> a >> b;
seg[i] = {l, b};
}
sort(seg.begin(), seg.end());
vector<array<int, 2>> a;
for(int i = 0; i < n; i++) {
if(!a.empty() && a.back()[1] >= seg[i][0]) {
a.back()[1] = max(a.back()[1], seg[i][1]);
} else {
a.push_back({seg[i][0], seg[i][1]});
}
}
int q;
cin >> q;
while(q--) {
int x;
cin >> x;
int p = lower_bound(a.begin(), a.end(), array{x + 1, 1}) - a.begin() - 1;
if(p >= 0) {
x = max(x, a[p][1]);
}
cout << x << " ";
}
cout << "\n";
}
标签:892,int,max,Codeforces,cin,seg,++,区间,Div
From: https://www.cnblogs.com/cenqi/p/17626698.html