有$N$個參賽者,每個參賽者有攻擊指數$a_i$和防禦指數$d_i$,每個參賽者可以往左或往右挑戰(可以往左往右一起來),如果兩個指數中一個大於對手且另一個不小於對手(攻擊對攻擊,防禦對防禦),那就會勝利。
如果勝利就能繼續往更左或更有挑戰,一路到沒有對手為止。
求最多勝場的參賽者的勝場數。
![](https://tioj.ck.tp.edu.tw/pimgs/2008/1.png)
![](https://tioj.ck.tp.edu.tw/pimgs/2008/2.png)
此時最大勝場數為8。
$1\le N\le 1.5\times 10^6, 0\le a_i,d_i\le 2\times 10^9$。
如果b能贏a且c能贏b則c能贏a,此時b能贏的人數決不會比c多。因此符合單調性。
維護一個非嚴格遞減的stack,對於每個元素pop掉stack中能贏過他們的,stack的top即為該元素可以往左挑戰到的最左端。
做一次從左到右和從右到左的聯集,之後取最大值即是答案。
複雜度$\mathcal{O}(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 48 49 50 51 52 53 54 55 56 57 58 59 60 61
|
#include <bits/stdc++.h> using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL); #define mem(i,j) memset(i,j,sizeof (i)); using ll = int64_t; using ull = uint64_t; using ld = long double; using uint = uint32_t; const double EPS = 1e-8; const int INF = 0x3F3F3F3F; const ll LINF = 4611686018427387903; const int MOD = 1e9+7;
signed main() { EmiliaMyWife
int n; cin >> n; vector<int> atk(n), def(n), ans(n); auto win = [&] (int a, int b) { return ((atk[a] == atk[b] && def[a] >= def[b]) || (atk[a] > atk[b] && def[a] >= def[b])); }; for(int i = 0; i < n; i++) cin >> atk[i] >> def[i]; stack<int> st; for(int i = 0; i < n; i++) { while(st.size() && win(i, st.top())) st.pop(); if(st.empty()) ans[i] += i; else ans[i] += i - st.top() - 1; st.push(i); } st = stack<int>(); for(int i = n - 1; ~i; i--) { while(st.size() && win(i, st.top())) st.pop(); if(st.empty()) ans[i] += n - i - 1; else ans[i] += st.top() - i - 1; st.push(i); } cout << *max_element(ans.begin(), ans.end()) << '\n';
return 0; }
|