题解 P1704 【寻找最优美做题曲线】

MorsLin

2019-05-18 17:23:20

Solution

把必须要做题的$K$天看作一个个端点 因为这$K$天是我们必须要做题的,而我们又要保证做题数量单调递增,所以我们可以在每两个端点之间筛选出大于左端点小于右端点的数,然后整体跑一遍最长上升子序列,这样就可以保证满足题目条件 无解的情况就是存在一个右端点大于等于右端点 看了一眼题解区,全是手写二分,在这里提供一个STL的做法 ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #define LL long long using namespace std; LL read() { LL k = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') k = k * 10 + c - 48, c = getchar(); return k * f; } int p[500010], a[500010], ans[500010], b[500010], tot; int main() { int n = read(), k = read(); for(int i = 1; i <= k; ++i) p[i] = read(); for(int i = 1; i <= n; ++i) a[i] = read(); sort(p+1, p+k+1); for(int i = 1; i <= p[1]; ++i) if(a[i] < a[p[1]]) ans[++tot] = a[i]; ans[++tot] = a[p[1]]; for(int i = 2; i <= k; ++i) { if(a[p[i-1]] >= a[p[i]]) { printf("impossible\n"); return 0; } for(int j = p[i-1]+1; j <= p[i]; ++j) { if(a[j] < a[p[i]] && a[j] > a[p[i-1]]) ans[++tot] = a[j]; } ans[++tot] = a[p[i]]; } for(int i = p[k]; i <= n; ++i) if(a[i] > a[p[k]]) ans[++tot] = a[i]; int cnt = 0; for(int i = 1; i <= tot; ++i) { if(ans[i] > b[cnt]) b[++cnt] = ans[i]; else { int pos = lower_bound(b+1, b+cnt+1, ans[i]) - b; b[pos] = ans[i]; } } cout << cnt << endl; return 0; } ```