[TIOJ]1617. [Interactive] 中位數

題目連結：http://tioj.infor.org/problems/1617

大家如果想一下肯定發現一個性質，Med3()對於三個數字，會回傳中間值，而掃過整個序列，必能找出最大值與最小值的位置，當然就可以透過這個方法，找n/2次，最後剩下的那個數字就是中位數，但這樣顯然會用太多次Med3()。
因為你已經找出這個序列的極值，那隨便找另外兩個數字和其中一個極值作Med3()會等同於比較那兩個數字的大小（因為極值不可能是中位數），因此可以用sort函式來排序，中間值就是中位數。

#include "lib1617.h"
#include <algorithm>
int a,b,n,k,v[1505];
int main(){
    n = Get_Box();
    if(n == 1)Report(1);
    a = 1;b = 2;
    for(int i = 3; i <= n ; i++){
        int k = Med3(a,b,i);
        if(a == k)a = i;
        if(b == k)b = i;
    }
    for(int i = 1 ; i <= n ; i++)if(i != a and i != b)v[k++] = i;
    std::sort(v,v+n-2,[](int x,int y){
        int tmp = Med3(a,x,y);
        return tmp == x ? 1 : 0;
    });
    Report(v[(n-2)/2]);
    return 0;
}

這樣只能拿40分。

不保證AC解法：
比中位數小的數字個數會等於比中位數大的數字個數，因此我們先找出這個序列的極值，然後隨機找一個數 t 並算出比 v[t] 小和大的個數，而整個序列的中位數在目前序列中會有 k 個數字比v[t]小，如果比v[t]小的數字個數剛好等於 k ，那就找到整個序列的中位數，如果> k 那就改成在比v[t]小的那個陣列內找答案，如果< k那就必須在比v[t]大的那個陣列找答案，且k要減l.size()+1。
顯然如果隨機數選的不好，還是很有可能WA。

#include "lib1617.h"
#include <vector>
#include <algorithm>
#include <ctime>
#define mid(x,y) (x+y)/2
#define PB push_back
using namespace std;
vector<int> v;
int a,b,n;
int find(int k){
    int t = rand()%v.size();
    vector<int> l,r;
    for(int i : v){
        if(i == v[t])continue;
        int k = Med3(i,v[t],a);
        if(k == i)r.PB(i);
        else l.PB(i);
    }if(l.size() == k)return v[t];
    else if(l.size() > k){
        v = l;
        return find(k);
    }else{
        v = r;
        return find(k-l.size()-1);
    }
}
int main(){
    srand(time(NULL));
    n = Get_Box();
    if(n == 1)Report(1);
    a = 1;b = 2;
    for(int i = 3; i <= n ; i++){
        int k = Med3(a,b,i);
        if(a == k)a = i;
        if(b == k)b = i;
    }
    for(int i = 1 ; i <= n ; i++)if(i != a and i != b)v.PB(i);
    Report(find((n-2)/2));
    return 0;
}

AC解法：
可以nth_element，這個函式可以在O(n)時間找到序列的第k個位置是誰且他的左邊放比他小的，右邊放比他大的。

#include "lib1617.h"
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;
vector<int> v;
int a,b,n;
int main(){
    n = Get_Box();
    if(n == 1)Report(1);
    a = 1;b = 2;
    for(int i = 3; i <= n ; i++){
        int k = Med3(a,b,i);
        if(a == k)a = i;
        if(b == k)b = i;
    }
    for(int i = 1 ; i <= n ; i++)if(i != a and i != b)v.PB(i);
    nth_element(v.begin(),v.begin()+(n-2)/2,v.end(),[](int x,int y){
        int tmp = Med3(a,x,y);
        return tmp == x ? 1 : 0;
    });
    Report(v[(n-2)/2]);
    return 0;
}