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;
}