Gym 100971D Laying Cables 二分 || 單調棧

要求找出每個a[i]，找到離他最近而且權值比它大的點，若距離相同，輸出權利最大的那個

我的做法有點複雜，時間也要500+ms，因為隻要時間花在了map上。

具體思路是模拟一顆樹的建立過程，對于權值最大的那個，必須是-1，次大的那個，必須是pos_peo[mx]；就是最大人口的節點id、

然後維護一個單調的序列，記錄目前有多少個位置加入了樹。用個set保證單調性。小到大

把結構體按人口排序大到小，枚舉沒個城市，這樣保證加入後，後面加入的直接找位置最短即可，人口最對的bigger than now的。

二分一個位置，> now.pos的，枚舉它左右，選擇即可。注意就是當距離相同的時候，還要再判斷一次。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 200000 + 50;
map<int,int>pos_peo;
map<int,int>pos_pos;
struct data {
    int pos,peo;
} a[maxn],b[maxn];
int ans[maxn];

struct cmp1 {
    bool operator()(int a,int b) {
        return a < b; //
    }
};
bool cmp2 (data a,data b)
{
    return a.peo > b.peo;
}
set<int,cmp1>SS;
void work ()
{
    int n;
    scanf ("%d",&n);
    int mx = -inf;
    for (int i=1; i<=n; ++i) {
        scanf ("%d%d",&a[i].pos,&a[i].peo);
        b[i].pos=a[i].pos;
        b[i].peo=a[i].peo;
        pos_peo[a[i].peo] = i; //id
        pos_pos[a[i].pos] = i;
        mx = max(mx,a[i].peo);
    }
    if (n==1) {
        printf ("-1\n");
        return ;
    }
    ans[pos_peo[mx]] = -1;
    int sec = -inf;
    for (int i=1; i<=n; ++i) {
        if (sec < a[i].peo && a[i].peo != mx)
            sec = a[i].peo;
    }
    ans[pos_peo[sec]] = pos_peo[mx];

    SS.insert(a[pos_peo[mx]].pos);
    SS.insert(a[pos_peo[sec]].pos);

    sort (a+1,a+1+n,cmp2); // peo up to low

    set<int>::iterator it;
    for (int i=3; i<=n; ++i) {
        int val = a[i].pos;
        int ppeo = a[i].peo;
        it = SS.lower_bound(val);
        int t1 = inf,t2 = inf;
        if (it == SS.begin()) { //在開頭
            ans[pos_peo[a[i].peo]] = pos_pos[*it];
        } else if (it == SS.end()) { //在末尾
            it --;
            ans[pos_peo[a[i].peo]] = pos_pos[*it];
        } else {
            int tt1 = *it;
            t1 = abs(val - (*it));
            it--;
            int tt2 = *it;
            t2 = abs(val - (*it));
            if (t1 < t2) {
                ans[pos_peo[a[i].peo]] = pos_pos[tt1];
            } else if (t1 > t2) {
                ans[pos_peo[a[i].peo]] = pos_pos[tt2];
            } else { //xiangdeng
                int id2 = pos_pos[tt1];
                int id1 = pos_pos[tt2];
                int cut2 = abs(b[id2].peo - ppeo);
                int cut1 = abs(b[id1].peo - ppeo);
                if (cut2 > cut1) {
                    ans[pos_peo[a[i].peo]] = pos_pos[tt1];
                } else {
                    ans[pos_peo[a[i].peo]] = pos_pos[tt2];
                }
            }
        }
        SS.insert(a[i].pos);
    }
    for (int i=1; i<=n; ++i) {
        printf ("%d ",ans[i]);
    }
    printf ("\n");
}
int main()
{
#ifdef LOCAL
    freopen("data.txt","r",stdin);
#endif
    work ();
    return 0;
}      

View Code

其實這個可以用單調棧O(n)解決

首先，對于任何一個city，隻有兩種可能，選擇在它左邊的第一個城市，或者選擇在它右邊的第一個城市，當然這些城市都是要合法的。就是要滿足人口數 > 目前城市。

是以首先對pos進行排序。這樣壓棧的時候就能知道相對位置了。用單調棧預處理ri[i]表示右邊第一個合法城市。le[i]同理。比較即可。

為什麼是第一個合法城市呢？第二個合法城市不行？這是因為距離要最短，要先滿足距離。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 200000 + 20;
struct node {
    int pos, val, id;
    bool operator < (const node &rhs) const {
        return pos < rhs.pos;
    }
}a[maxn], ri[maxn], le[maxn];
int stack[maxn], ans[maxn];
void work ()
{
    int n;
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf ("%d%d", &a[i].pos, &a[i].val);
        a[i].id = i;
    }
    sort (a + 1, a + 1 + n);
    int top = 0;
    for (int i = 1; i <= n; ++i) {
        while (top >= 1 && a[i].val > a[stack[top]].val) --top;
        ++top;
        stack[top] = i;
        if (top != 1) {
            le[i] = a[stack[top - 1]];
        } else {
            le[i].id = -inf;
        }
    }
    top = 0;
    for (int i = n; i >= 1; --i) {
        while (top >= 1 && a[i].val > a[stack[top]].val) --top;
        ++top;
        stack[top] = i;
        if (top != 1) {
            ri[i] = a[stack[top - 1]];
        } else {
            ri[i].id = -inf;
        }
    }
    for (int i = 1; i <= n; ++i) {
        int toans;
        if (le[i].id == -inf) {
            toans = ri[i].id == -inf ? -1 : ri[i].id;
        } else if (ri[i].id == -inf) {
            toans = le[i].id == -inf ? -1 : le[i].id;
        } else {
            int posL = abs(le[i].pos - a[i].pos);
            int posR = abs(ri[i].pos - a[i].pos);
            if (posL > posR) {
                toans = ri[i].id;
            } else if (posL == posR) {
                if (le[i].val > ri[i].val) {
                    toans = le[i].id;
                } else {
                    toans = ri[i].id;
                }
            } else {
                toans = le[i].id;
            }
        }
        ans[a[i].id] = toans;
    }
    for (int i = 1; i <= n; ++i) {
        printf ("%d ", ans[i]);
    }
}

int main ()
{
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    work ();
    return 0;
}