UVa1611 Crane [思维/模拟]
我原本还是能够想出解法的...
然而事实上我还是考虑过多了...
大概说明我不擅长骗分....
Problem
输入 n 个数要求把它变成升序排列,每次操作都可以交换一个长度为偶数区间的左右两半
$n\leq 10000$
有多组数据
Solution
题目给开了三秒。
正解思路是每次找序列最小值。
然后用 $\leq 3$ 次操作旋到对应的位置。
所以每次对一个值操作可以用不超过 $O(2n)$ 的时间。
因此时间复杂度是 $O(n^2)$ 的。
理论上数据不超过三组可过。
但我掐指一算,数据肯定不止三组呀?
于是我就没用这个方法了。
我用了个更蠢的
就是冒泡排序法
先随机交换个 100 遍再说
果然炸了
于是换成了原来的方法
210ms....
Code
// Code by ajcxsu
// Problem: crane
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int arr[N];
int n;
void inv(int l, int r) {
int mid=l+(r-l+1)/2;
while(mid<=r) swap(arr[l++], arr[mid++]);
}
int opt[1000000][2], p;
int main() {
srand(time(NULL));
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
cin>>n;
p=0;
int nl, nr, len;
for(int i=1;i<=n;i++) cin>>arr[i];
for(int i=1;i<=n;i++) {
for(nr=i;nr<=n;nr++)
if(arr[nr]==i) break;
len=nr-i+1;
if(len==1) continue;
else if(len==2) inv(i, i+1), opt[++p][0]=i, opt[p][1]=i+1;
else if(len&1) {
inv(i+1, nr);
inv(i, nr-1);
opt[++p][0]=i+1, opt[p][1]=nr;
opt[++p][0]=i, opt[p][1]=nr-1;
}
else {
inv(i+2, nr);
inv(i+1, nr-1);
inv(i, i+1);
opt[++p][0]=i+2, opt[p][1]=nr;
opt[++p][0]=i+1, opt[p][1]=nr-1;
opt[++p][0]=i, opt[p][1]=i+1;
}
}
cout<<p<<endl;
for(int i=1;i<=p;i++)
cout<<opt[i][0]<<' '<<opt[i][1]<<endl;
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-uva-1611.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆