[洛谷春令营 省选第一次模拟T2] 最长不下降子序列【二分+归并排序】

  • 2018-02-15
  • 0
  • 0

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

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai