【高速選択アルゴリズムとnth_element関数】【継続UVA 11300】

2797 ワード

白書の中でO(n)レベルの中位数を探すアルゴリズムが今日紹介する主役です
クイックセレクトアルゴリズム
速い列のように1つの比較要素を選択して再帰処理してk番目の大きい要素を探します
最後に要素をiに比較したと仮定する
以下の説明は私が速い列の常用文字を書くので、外部の人は理解できないはずです...
(i-s+1)(i-s+1)=kがiの値を返却すればよい
(i-s+1)>kが行く(s,i-1)区間が再帰的にk番目に大きい数を探すと
速い列のような考えは分かりやすい.
コードは次のとおりです.

int swap(long long &a,long long &b) {long long temp=a;a=b;b=temp;return 0;}
int quickchoice(long long *A,int s,int t,int k)
{
	int i=s,j=t;
	long long x=A[s];
	while(i<j)
	{
		while(i<j&&A[j]>=x) j--;
		if(i<j) swap(A[i],A[j]),i++;
		while(i<j&&A[i]<x)  i++;
		if(i<j) swap(A[j],A[i]),j--;
	}
	A[i]=x;
	if((i-s+1)==k) return 0;
	else if((i-s+1)<k&&i+1<=t) quickchoice(A,i+1,t,k-(i-s+1));
	else if((i-s+1)>k&&s<=i-1) quickchoice(A,s,i-1,k);  
	return 0;
}

UVA 11300高速選択アルゴリズムは以下のように実現される.

#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
long long gold[1000100],M;
int cmp(const void *i,const void *j)
{
	if(*(long long *)i>*(long long *)j) return 1;
	else if(* (long long *)i==*(long long *)j) return 0;
	else return -1;
}
int main()
{
	int n,k;
	long long sum;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&gold[i]);
			sum+=gold[i];
		}
		M=sum/n;
 		for(int i=1;i<=n-1;i++)
		gold[i]=gold[i-1]+M-gold[i];
		gold[n]=0;
		qsort(gold+1,n,sizeof(gold[1]),cmp);
		k=(n+1)/2;
		sum=0;
		for(int i=1;i<=n;i++)
		sum=sum+abs(gold[i]-gold[k]);
		printf("%lld
",sum);
	}
	return 0;
}

上の方法では、なぜ速度と速列に違いがないのか分かりません.
でも次は倍近く
nth_Element関数は非常に奇妙です
ネット上の様々な奇抜な資料に誤解されているのがおかしいと思います
自分の手で操作してわかった
nth_element(begin,kth,end)
[begin,end)の区間でk番目に大きい数を探すのは実はこのような記述が正確ではない.
このような説明はもっと適切なようだ.
例えばnth_element(s+1,s+k,s+n+1)
[1,n+1)この区間におけるs[k]左側のすべてが彼の右側のすべてが彼のものより大きいことに等しい.
区間が1からk番目に記述できるようなら
1から注意しないと
MACコードは以下の通りである.

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long gold[1000100],M;
int n;
int main()
{
	int k;
	long long sum;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&gold[i]);
			sum+=gold[i];
		}
		M=sum/n;
 		for(int i=1;i<=n-1;i++)
		gold[i]=gold[i-1]+M-gold[i];
		gold[n]=0;
		k=(n+1)/2;	
		nth_element(gold+1,gold+k,gold+1+n);
		for(int i=1;i<=n;i++)
		printf("gold:%d
",gold[i]);
		sum=0;
		for(int i=1;i<=n;i++)
		sum=sum+abs(gold[i]-gold[k]);
		printf("%lld
",sum);
	}
	return 0;
}

ブルーブリッジカップブロック数DFS検索

情報要約アルゴリズム-CRC(サイクル冗長検査)