CSP Week 4 ProblemC二分解答中位数問題を解く

18897 ワード
CSP精進の道
文書ディレクトリ
  • 総説
  • 題叙述
  • テーマ概要
  • INPUT
  • OUTPUT
  • 入力サンプル
  • 出力サンプル
  • 題意再述
  • 解題構想
  • まとめ
  • テーマソース
    • 総説
    すべての問題を始める前に、まず二分が何なのかを明らかにすることが重要で、二分の基礎知識を熟練してこそ、二分アルゴリズムの基礎の上で、二分解答アルゴリズムを理解し、相応の問題を解くことができる.二分の説明は幅が大きいので、ここで隣の園の超詳細な説明を導入します.まずしっかりした二分アルゴリズムの基礎を身につけてから、本編の読書を始めてください.ここは転送ドアです.
    テーマ叙述
    テーマの概要
    TTは重度の猫好きで、毎日B駅の猫チャンネルに溺れている.ある日、TTの親友ZJMはTTに難題を任せることにした.TTがこの難題を解決できれば、ZJMはかわいい猫を買ってTTにあげる.タスク内容は,N個の数の配列cat[i]を与え,この配列で新しい配列ans[i]を生成する.新しい配列は、任意のi,j,i!=jは,いずれもans[]=abs(cat[i]−cat[j]),1<=iINPUT
    複数組の入力は、N個の数を表すNを1個ずつ入力し、その後、N個の長さのシーケンスcatを入力し、cat[i]<=1 e 9、3<=n<=1 e 5
    OUTPUT
    新しい配列ansの中位数を出力
    入力サンプル
    4 1 3 2 4 3 1 10 2
    出力サンプル
    1 8
    題意を改めて述べる
    テーマは抽象的ではなく、非常に理解しやすいが、このようにすればするほど、掘った穴が深くなる整数配列があり、配列ans[]を生成し、その要素を満たすようになります.
    ans[] = abs(cat[i] - cat[j])
    タスク時にこの新しい配列の中位数の大きさを解いて、データの大きさは1 e 5です
    問題を解く構想.
    タイトルの最初の目を見ると、これは何の問題なのか、水が多すぎて複雑ではないと思うかもしれませんが、直接暴力が上手になるとTLEは暴力のやり方を思い出して、n点を処理して、新しい配列ans[]を生成する時にO(n^2)の時間の複雑さを使って、これはタイトルが要求する1 msの時間内に完成することはできません.それはおかしいかもしれませんが、どうやって最適化しますか???難点1:二分関数を導入し,その正しさを判断する際には,生成配列を計算せずに中位数を求める二分解答法を導入する必要がある.前の学習を経て、あなたは理解するべきです:区間内の動きが単調であれば、このテーマの中で二分することができて、配列値は直接解くことができなくて、だから配列値の単調性は利用できなくて、私達は1種の指標を求めて配列の単調性に取って代わってそして2分の解を行う必要があります.中位数を計算するとき,配列値は単調に増加し,上位の要素値も必ず上位より高くなるという推論により,配列値の二分を順位の二分に変換できる.しかしABS()関数の非単調性に限られ,直接順位の解を行うことはできず,現在の配列の単調性を先にsort()並べ替えて保証し,順位を解く方式を採用し,計算に参加するすべての要素が一致する単調性を保証し,順位を用いて2点を開始することができる.難点2:解ランキングは目標数列が知られていないため,ランキングの解は従来のソート方法では行えない.上記のアルゴリズムの解の過程で,1つの数字aを得てその順位を解くたびに,実質的には
    {対(i,j)求和|i,jはxj-xi<=aを満たす}
    この問題を解決するには、iを列挙することができ、1回の解のサイクルの中で、iを1つの定値と見なし、aも1つの定値と見なし、このアルゴリズムは条件を満たすjが現れる最後の位置を解くことに変換することができ、配列はすでに秩序が単調であるため、私たちは再び整数二分解を使用することができる.これにより,問題を解く過程ですべての問題が解決され,その問題の難点が解消される.易誤点問題の難点はすでに私たちに分析されているが、実現過程ではいくつかの易誤点に穴を踏みやすい.第1回はこの問題を実現して、参照を調整するのはとても苦痛な1件の事かもしれなくて、具体的なパラメータの分析は詳しくコードと関連する注釈を見ます
    int search_mid(int num)//      ：             ，             ，           (    )      
{
	int left=0;
	int right=a[num-1]-a[0];
    int mid=0;
    int ans=-1;
	int mid_pos=(num*(num-1)/2+1)/2;
    while(right>=left)
    {
    	int rank=0;
        mid=(left+right)/2; 
        for(int i=0;i<num;i++)
        {
            int flag=search_j(a[i]+mid,0,num-1);
            if(flag!=-1)
            rank+=(flag-i);
        }
        if(rank>=mid_pos)
//           ，          ，             
//     rank       i-j<=p,      P          ，                 
//      4 4 4 8 8 12， 5,6,7，   rank   3，    5 6 7       ，  ：     ，  >n,
//      4 4 4 8 8 12     ，6 rank==3，           ---
//    ：rank                     ，              
//               
        {
            right=mid-1;
            ans=mid;
        }
        else
        left=mid+1;
    }
    return ans;
}

    まとめ
    このアルゴリズムは上記のように最適化され,時間的複雑度は約O(n(logn)^2)であり,問題の要件を満たすことができる.このテーマを実現する前に、二分はまだ愚かで、何が二分の答えなのか分からない.ターゲット配列が何なのか分からないのに、中位数を求めるわけにはいかない.数回の繰り返し実現コードと研究を経て、二分答えには以下のような総括がある:二分答えは整数二分の高次変種である.二分答えは答えが存在する可能性のある区間内で、生成された単調性が一致するパラメータを変換し、絶えず二分して最終的に答えの具体的な実現テンプレートを探し出す:二分答えのテーマの中で、往々にして目標の配列は求められないか、タイムアウトするか、つまり整数二分の目標区間がない.我々が解決しなければならないのは,目標区間の代わりに時間複雑度の制限内で求められる指標を探し出し,二分を達成することである.この指標を見つけた後,二分する方法は,答えの上下限を二分の上下限とし,その領域内のすべての要素を検索し二分処理し,最終的に答えを見つけることである.
    テーマソース
    #include
#include
#include 
using namespace std;
int a[100001];
int search_j(int find_b,int left,int right)//  j (    find_b      )
{
    int ans=-1;
    int mid=0;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(a[mid]<=find_b)
        {
            ans=mid;
            left=mid+1;
        }
        else
        right=mid-1;
    }
    return ans;
}
int search_mid(int num)
{
	int left=0;
	int right=a[num-1]-a[0];
    int mid=0;
    int ans=-1;
	int mid_pos=(num*(num-1)/2+1)/2;
    while(right>=left)
    {
    	int rank=0;
        mid=(left+right)/2; 
        for(int i=0;i<num;i++)
        {
            int flag=search_j(a[i]+mid,0,num-1);
            if(flag!=-1)
            rank+=(flag-i);
        }
        if(rank>=mid_pos)
        {
            right=mid-1;
            ans=mid;
        }
        else
        left=mid+1;
    }
    return ans;
}
int main()
{
    int number=0;
    while(scanf("%d",&number)!=EOF)
    {
    for(int i=0;i<number;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+number);
    int result=search_mid(number);
    cout<<result<<endl;
    }
    return 0;
}
    golang struct tag
    Jsonソース翻訳