首页 > 代码库 > Gym 100971D Laying Cables
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;}
Gym 100971D Laying Cables
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。