簡単なアルゴリズムの小さい応用

2784 ワード

最近、牛客ネット上でアルゴリズムの練習をよく行い、2つの面白いテーマを共有しています.
牛客网のリンクを添付して、もちろん、ACM大神と比べて、これらの问题は入门的で、学びたい子供靴は温故知新しましょう.そうだ、これは比較的良いプラットフォームで、みんなは大丈夫で手を練習することができます.
ソートの問題
なぜこの問題がソートアルゴリズムに分けられたのか分からないが、私はこの問題を書くとき、効率を高めるために二分検索、速排などのアルゴリズムを使って、依然としてタイムアウトして、本当に悲しいです.その後、私は複雑なソートを削除して、直接暴力的に解いて、かえっていいです.
伝送門は以下の通りである:牛客網
問題は以下の通りです.
ここではmap構造を使用して主なデータを格納しています.もちろん、効率が最も高いメモリは配列を使用しています.しかし、私は分かりやすいように配列を使っていません.基数ソートの考え方に従って、私は映画の言語を対応する下付きの配列の中に存在して、このような検索効率は最も高くて、あなたがどのようにソートしても、毎回遍歴するのはとても時間がかかりますから.もう一つの小さなポイントは、配列の下付き文字に頻繁にアクセスする(同じ下付き文字でも)よりも、一時変数で格納する方が効率的であることです.

#include
#include
#include
using namespace std;

struct Movie{
    int bj;
    int cj;
    int scoreb;
    int scorec;
    int index;
};
int main()
{
    int n,m,firstScore=0,secondScore=0,index=1;
    cin >> n;
    map strMap;
    for(int i = 0; i < n;i++){
        int temp;
        cin >> temp;
        strMap[temp]++;
    }
    cin >> m;
    Movie ret[m];
    for(int i = 0; i < m;i++){
        //        
        ret[i].cj = 0;
        ret[i].bj = 0;
        ret[i].scoreb = 0;
        ret[i].scorec = 0;
        ret[i].index = i+1;
        cin >> ret[i].bj;
    }
    //sort(a, a+n);
    for(int i = 0; i < m;i++){
        cin >> ret[i].cj;
        //       temp  ，     ，        
        //ret[i].scoreb = caculateNum(ret[i].bj,a,n);
        //ret[i].scorec = caculateNum(ret[i].cj,a,n);
        int tempb = strMap[ret[i].bj];
        int tempc = strMap[ret[i].cj];
        int tempi = ret[i].index;
        if(tempb >= firstScore){
            if(tempb > firstScore){
                firstScore = tempb;
                secondScore = tempc;
                index = tempi;
            }else{
                if(tempc > secondScore){
                    secondScore = tempc;
                    index = tempi;
                }
            }

        }
    }
//    sort(ret, ret+m, CmpByValue());
    cout<

並べ替え問題2
このテーマは比較的に簡単で、1つのソートの後で、最も良い過程を求めます.
伝送門は以下の通りである:牛客網
問題は以下の通りです.
直感的に考えて、仮に私たちがk番目の店の座標に倉庫を建てたら、倉庫の左側にk-1つの店があり、右側にn-k-1つの店があり、倉庫を右に1つの単位を移動すると、倉庫の左のすべての店からの距離が1つの単位増加し、右のすべての店からの距離が1つの単位減少します.したがって、左右の店の個数を同じにしなければならない.k−1=n−k−1であれば、k=n/2、kはシーケンス全体の中位数の位置である.

#include 
#include 

using namespace std;

const int N = 100010;

int a[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    int spc = a[n >> 1];
    int res = 0;

    for (int i = 0; i < n; i++)
        res += abs(a[i] - spc);

    cout << res << endl;
}

Pythonフォームデータのコミット

コンピュータネットワークのリンク状態ルーティングアルゴリズム(LS)