听说了这个OJ在搞刷题活动，就来水题了
\(Markdown\)修题面修了半天，以后再也不修了\(QwQ\)
题目链接
众所周知，排序方法有许多种。例如：简单易懂的冒泡排序，平均复杂度较优的快速排序，以及不基于比较的基数排序等等。
现在，小\(D\)得到了一个自然数序列\({a_1,a_2,?,a_n}\)。他想要对其按照从小到大的顺序进行排序（即使得每个元素均严格不大于他的后继元素）。但由于基于比较的排序算法复杂度下界已经被证明为\(Θ(nlog2n)\)，所以小\(D\)决定尝试一种全新的排序算法：翻转排序。
在翻转排序中，小 \(D\) 在每次操作中，可以选择一个区间 \([l,r] (1≤l≤r≤n)\)，并翻转 \(a_l,a_{l+1},?,a_r\)。即，在该次操作完后，序列将会变为 \(a_1,a_2,?,a_{l?1},a_r,a{r?1},?,a_{l+1},a_l,a_{r+1},a_{r+2},?,a_n\)。
例如，对于序列 \([1,6,2,4,3,5]\)，若选择区间 \([2,4]\) 进行翻转，则将会得到 \([1,4,2,6,3,5]\)。
定义一次操作的代价为 \(r?l+1\)，即翻转的区间长度。定义一个操作序列的代价为每次操作的代价之和。现在，请你帮助小 \(D\) 求出一个代价足够小的操作序列（你并不一定要求出代价最小的操作序列）。
第一行一个正整数\(n\)，表示序列长度。
第二行\(n\)个空格隔开的非负整数，表示小\(D\)得到的自然数序列\({{a_i}}\)。
输出若干行，每行两个空格隔开的正整数 \(l,r\) \((1≤l≤r≤n)\)，表示一次翻转区间\([l,r]\)的操作。
最后输出一行\(-1 -1\)，标志着操作序列的结束。
4 1 3 2 4
2 3 -1 -1
1.下发文件中提供了 \(checker.cpp\)，该程序将对于其所在目录下的 \(sort.in\)，判断其所在目录下的 \(sort.out\) 是否为一个正确的操作序列。若正确，将给出该操作序列的代价。若不正确，将给出错误信息。选手可以借助该程序来更好地检查自己的程序是否正确。
运行时，必须保证 \(sort.in\) 为一个合法的输入，且需保证 \(sort.out\) 符合题目中描述的输出格式，否则出现任何结果均有可能。
#include <algorithm>
#include <cstdio>
int arr[50005];
int main()
{
FILE *fin = fopen("sort.in", "r"), *fout = fopen("sort.out", "r");
if (!fin)
{
puts("INVALID : File sort.in not found.");
return -1;
}
if (!fout)
{
puts("INVALID : File sort.out not found.");
return -1;
}
int n;
fscanf(fin, "%d", &n);
for (int i = 0; i < n; i++)
fscanf(fin, "%d", arr + i);
int l, r, sum = 0;
while (~fscanf(fout, "%d%d", &l, &r))
{
if (l == -1 && r == -1)
break;
sum += r - l + 1;
if (l <= 0 || l > n)
{
printf("INVALID : l = %d is not in range [1, %d].\n", l, n);
return -1;
}
if (r <= 0 || r > n)
{
printf("INVALID : r = %d is not in range [1, %d].\n", r, n);
return -1;
}
if (l > r)
{
printf("INVALID : %d = l > r = %d.\n", l, r);
return -1;
}
if (sum > 20000000)
{
puts("INVALID : Too much cost.");
return -1;
}
std::reverse(arr + --l, arr + r);
}
bool f = true;
for (int i = 1; i < n; i++)
f &= arr[i] >= arr[i - 1];
if (!f)
{
puts("INVALID : Not sorted.");
return -1;
}
printf("VALID : Total cost is %d.\n", sum);
return 0;
}2.对于所有测试数据，保证 \(1≤n≤50000\)，且 \(0≤ai≤10^9\)。
还是一道比较有思维含量的题，结合了快速排序和归并排序的思想。
考虑\(85%\)的部分分(即\(5000\)以下的数据点和\(01\)串)
对于\(01\)串，我们考虑类似归并排序的形式，分治下去，回溯时左半部分的右边均为\(1\)，右半部分的左边均为\(0\)，进行一次\(Reverse\)即可
再考虑\(100%\)，我们可以类似快速排序，选择一个基准数\(stdq\)，将满足\(a_i<=stdq\)的\(a_i\)视为\(0\)，\(1\)同理，再按\(85%\)的方法处理即可
在代码实现的过程中，我们用离散化来实现，其中\(pre[]\)用于维护大小关系，具体见代码
#include<bits/stdc++.h>
using namespace std;
namespace my_std
{
typedef long long ll;
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define pf printf
inline ll read()
{
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
sum=(sum<<1)+(sum<<3)+(ch^48);
ch=getchar();
}
return sum*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
}
using namespace my_std;
const int N=5e4+50;
int n,pre[N],stdq;
struct qq
{
int v,val;
}a[N];
bool cmp(qq a,qq b)
{
return a.v<b.v;
}
inline void work(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>1;
work(l,mid),work(mid+1,r);
int lefty=mid,righty=mid,lp=mid,rp=mid+1;
while(lp>=l&&pre[lp]>stdq) lefty=lp--;
while(rp<=r&&pre[rp]<=stdq) righty=rp++;
if(lefty!=righty)
{
pf("%d %d\n",lefty,righty);
reverse(pre+lefty,pre+righty+1);
}
}
inline void mergesort(int l,int r)
{
if(l==r) return;
int mid=stdq=(l+r)>>1;
work(l,r);
mergesort(l,mid),mergesort(mid+1,r);
}
int main(void)
{
n=read();
fr(i,1,n)
{
a[i].v=read();a[i].val=i;
}
sort(a+1,a+n+1,cmp);
fr(i,1,n) pre[a[i].val]=i;
mergesort(1,n);
puts("-1 -1");
return 0;
}原文：https://www.cnblogs.com/lgj-lgj/p/12332542.html