山东省第五届ACM省赛 Weighted Median

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define inf 0x3f3f3f3f
#define lln long long int
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(b, -1, sizeof(b))
#define deb(x, n) cout << (x) << " " << (n) << endl
#define cr printf("\n")
// 调试用
    template <class type>
void debug(type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
const int maxn = 10000000+10;
lln sum[maxn];
struct ele
{
    lln x, w;
};
int cmp(ele a, ele b)
{
    return a.x < b.x;
}
ele e[maxn];
int main()
{
#ifdef debug
    // freopen("input", "r", stdin);
#endif
    int n;
    while(scanf("%d", &n) != eof)
    {
        for(int i = ; i < n; i++) scanf("%lld", &e[i].x);
        for(int i = ; i < n; i++) scanf("%lld", &e[i].w);
        sort(e, e+n, cmp);
        sum[] = e[].w;
        for(int i = 1; i < n;i ++) sum[i] = e[i].w + sum[i-1];
        double sm = sum[n-1]/2.0;
        bool flag;
        int i;
        for(i = ; i < n; i++)
        {
            int ti, tj;
            ti = tj = i;
            if(i != ) while(e[ti].x == e[ti-1].x) ti--;
            else ti = -1;
            if(i != n-1) while(e[tj].x == e[tj+1].x) tj++;
            else tj = n;
            flag = 1;
            // wi <= s/2
            if(ti == -1) {}
            else if(sum[ti-1] <= sm) {}
            else flag = ;
            // wi < s/2
            if(tj == n) {}
            else if (sum[n-1] - sum[tj] < sm){}
            else flag = ;
            if(flag) break;
            i = tj;
        }
        printf("%lld\n", e[i].x);
    }
    return ;
}