[洛谷春令营 省选第一次模拟T2] 最长不下降子序列【二分+归并排序】
Problem:
题目描述
给出一个长度为 n 的整数序列,你能够使用的操作只有 rev(l, r),表示将闭区间 [l, r] 内的数字翻转,需要的代价是 r-l+1,你需要在 4×106 的代价内最大化最终序列的 LIS 长度,LIS 表示最长不下降子序列。
只有你使用的操作的代价不超过限制,并且最终得到的序列的 LIS 和理论上能够得到的最大值一样的时候,才可以得分。
输入输出格式
输入格式:
第一行一个整数 n 表示序列长度。
接下来一行 n 个整数,表示序列。
输出格式:
输出第一行一个整数,表示使用的操作的数量。
接下来输出若干行操作,每行两个整数 l, r,表示一次操作。
如果有多种方案,输出任意一种即可。
输入输出样例
输入样例#1:
5 3 2 1 5 4
输出样例#1:
2 1 3 4 5
说明
对于所有数据,满足 n≤32000,0≤序列中的数字≤32000
Subtask1[10pts]
n≤100
Subtask2[10pts]
n≤1000
Subtask3[10pts]
0≤序列中的数字≤5
Subtask4[10pts]
无特殊限制
Solution:
# 我的 Code 竟然跑了 rank 1 !!! #
本题题目叫作“最长不下降子序列”,但是实际上是道排序题。
直接用 O(n2) 的冒泡排序,将交换看作长度为 2 的序列翻转,就可以水到 30 分。。(我不会告诉你比赛的时候我就是这么做的。。)
所以我们考虑基于 log 级别分治的归并排序。
显然直接二路归并不能支持翻转操作。。
我们考虑 01 归并,即将两个有序 01 序列合并时的情景:
- => 0 0 0 0 1 1 1 1 1 1|0 0 0 0 0 0 1 1 1 1
- => 0 0 0 0[1 1 1 1 1 1 0 0 0 0 0 0]1 1 1 1
- => 0 0 0 0[0 0 0 0 0 0 1 1 1 1 1 1]1 1 1 1
- => 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
除去子序列为全 0 或全 1 时的特判,每次合并都可以看成一次区间翻转。
我们二分枚举值域内的值,把大于该值的数看作 1,小于等于该值的数看作 0。
那么就可以通过 log 级别次 01 归并的翻转操作来实现升序排列。
最大代价与时间复杂度相同,卡满为 0.5nlog2n ≈ 3583596 < 4×106。(归并排序自带常数 0.5)
Code: O(nlog2n) [3402K, 40MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; inline void getint(int &num){ char ch; while(!isdigit(ch = getchar())); num = ch - '0'; while(isdigit(ch = getchar())) num = num * 10 + ch - '0'; } int n, a[32005]; int ansl[4000000], ansr[4000000], ans = 0; inline void Merge_Sort(int a[], int l, int r, int key){ if(l >= r) return; int mid = l + r >> 1; Merge_Sort(a, l, mid, key); Merge_Sort(a, mid + 1, r, key); int revl, revr; for(revl = l; a[revl] <= key && revl <= mid; revl++); for(revr = mid + 1; a[revr] <= key && revr <= r; revr++); if(revl > mid || --revr <= mid) return; ansl[++ans] = revl, ansr[ans] = revr; for(; revl < revr; revl++, revr--) swap(a[revl], a[revr]); } inline void solve(int a[], int l, int r, int vl, int vr){ if(l >= r || vl >= vr) return; int key = vl + vr >> 1; Merge_Sort(a, l, r, key); int mid = lower_bound(a + l, a + r + 1, key + 1) - a; // Find the first larger one solve(a, l, mid - 1, vl, key); solve(a, mid, r, key + 1, vr); } int main(){ getint(n); for(register int i = 1; i <= n; i++) getint(a[i]); solve(a, 1, n, -1, 32000); printf("%d\n", ans); for(register int i = 1; i <= ans; i++) printf("%d %d\n", ansl[i], ansr[i]); return 0; }
发表评论