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 ; }