777
技術社區[雲棲]
zoj 長沙 Bizarre Routine 模擬
題目給了個快排程序，要求構造序列使比較次數等於except。
於是給定n，我們可以求出可以到達的最小比較次數，和最大比較次數，n*（n-1)/2
根據快排，每次劃分，左邊是比其小的數，右邊是大的。因此如果劃分序列，隻需讓ans[m]=m;即可劃分為m-l-1和r-mid兩個，比賽的時候就這裏沒想清楚。
而最小值和(Min[x]+Min[len-x])最大值和都是單調遞減的,二分即可
最後再交換兩次，回到k位置即可
其實整個過程就是模擬下快排的逆過程
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int Low[10005];
int A,B;
int ans[10005];
int Mi(int n)//確定下界
{
if(n<=1)return 0;
if(~Low[n])return Low[n];
return Low[n]=Mi(n/2)+Mi(n-1-n/2)+n-1;
}
void solve(int l,int r,int e)
{
if(l>r)return;
if(l==r)
{
ans[l]=l;
return;
}
int len=r-l;
int ll=0,rr=(len+1)>>1,mid;
e-=len;
while(ll<rr)//二分查找劃分長度
{
mid=(ll+rr)>>1;
if(Mi(mid)+Mi(len-mid)>e)ll=mid+1;
else rr=mid;
}
mid=ll+l;
solve(l,mid-1,Mi(ll));
solve(mid+1,r,e-Mi(ll));
ans[mid]=mid;
swap(ans[mid],ans[r]);
swap(ans[r],ans[(A*l+B*r)/(A+B)]);//返回標兵
}
int main()
{
int n,e;
memset(Low,-1,sizeof(Low));
while(~scanf("%d%d%d%d",&n,&e,&A,&B))
{
if(Mi(n)>e||n*(n-1)/2<e) puts("NOWAY");
else
{
solve(1,n,e);
for(int i=1;i<=n;i++)
{
if(i>1)putchar(' ');
printf("%d",ans[i]);
}
puts("");
}
}
}
#include <cstdio>
#include<iostream>
#include <algorithm>
using namespace std;
int T,A,B;
bool less_than(int x, int y) {
T++;
return x < y;
}
void work(int array[], int l, int r) {
if (l >= r) return;
swap(array[(l * A + r * B) / (A + B)], array[r]);
int index = l;
for (int i = l; i < r; i++)
if (less_than(array[i], array[r]))
swap(array[index++], array[i]);
swap(array[r], array[index]);
work(array, l, index - 1);
work(array, index + 1, r);
}
int array[100000];
int main() {
int n,expect;
while(~scanf("%d%d%d%d",&n,&expect,&A,&B))
{
T=0;
for(int i=0;i<n;i++)
scanf("%d",&array[i]);
work(array, 0, n - 1);
if (T == expect)
puts("YES");
else
puts("NO");
}
}
最後更新：2017-04-03 15:21:56