USACO 2017 December Contest Gold T1: A Pie for a Pie

题目大意

Bessie和Elsie各自烤了 $N(1≤N≤10^5)个馅饼。Bessie 会这 2N 个馅饼打分，Elsie 也会。二者的打分均为一个 ≤1e9 的非负整数。由于她们口味不同，每个派的两个分数可能不同。她们想互赠礼物。开始时，Bessie 送给 Elsie 一个馅饼。她们收到礼物（对方做的馅饼）后都会回赠对方一个自己做的馅饼。她们选择回礼的方法相同。以 Elsie 为例，Elsie 根据自己的打分来选择回礼。回礼的分数至少要大于她收到的馅饼的分数，但两个馅饼的分数差不能大于 D(0≤D≤10^9) 。如果有多个馅饼满足要求，Elsie 可以选择其中的任意一个作为回礼。$

建图时应对每个两人的pie分别排序，这样便于二分建图。

（虽然此算法可能被卡成N²的，但由于出题人都是懒的，所以可以通过）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=400005;
 4 const int Inf=0x3f3f3f3f;
 5 struct Node{
 6     int bv,ev,id;
 7 }pb[MAXN],pe[MAXN];
 8 
 9 inline bool cmpb(Node x,Node y){
10     return x.bv<y.bv;
11 }
12 inline bool cmpe(Node x,Node y){
13     return x.ev<y.ev;
14 }
15 struct FboB{
16     inline bool operator()(const Node &x,const Node &y){
17         return x.bv<y.bv;
18     }
19 };
20 struct FboE{
21     inline bool operator()(const Node &x,const Node &y){
22         return x.ev<y.ev;
23     }
24 };
25 
26 struct Edge{
27     int to,nxt;
28 }e[MAXN<<4];
29 int cnt,head[MAXN<<1];
30 inline void add_edge(int u,int v){
31     e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
32 }
33 int n,d;
34 queue<int> q;
35 int dis[MAXN<<1];
36 inline void bfs(){
37     while(!q.empty()){
38         int x=q.front();
39         q.pop();
40         for(int i=head[x],y;i;i=e[i].nxt){
41             y=e[i].to;
42             if(dis[y]!=-1) continue;
43             dis[y]=dis[x]+1;
44             q.push(y);
45         }
46     }
47 }
48 int main(){
49     memset(dis,-1,sizeof(dis));
50     scanf("%d%d",&n,&d);
51     for(int i=1;i<=n;++i){
52         scanf("%d%d",&pb[i].bv,&pb[i].ev);
53         if(pb[i].ev==0){
54             dis[i]=1;
55             q.push(i);
56         }
57         pb[i].id=i;
58     }
59     for(int i=1;i<=n;++i){
60         scanf("%d%d",&pe[i].bv,&pe[i].ev);
61         if(pe[i].bv==0){
62             dis[i+n]=1;
63             q.push(i+n);
64         }
65         pe[i].id=i+n;
66     }
67     sort(pb+1,pb+n+1,cmpb);
68     sort(pe+1,pe+n+1,cmpe);
69     for(int i=1,pos;i<=n;++i){
70         Node tmp;
71         tmp.bv=pe[i].bv;
72         tmp.ev=pe[i].bv;
73         pos=lower_bound(pb+1,pb+n+1,tmp,FboB())-pb;
74         for(int j=pos;j<=n;++j){
75             if(pb[j].bv>pe[i].bv+d) break;
76             add_edge(pb[j].id,pe[i].id);
77         }
78     }
79     for(int i=1,pos;i<=n;++i){
80         Node tmp;
81         tmp.bv=pb[i].ev;
82         tmp.ev=pb[i].ev;
83         pos=lower_bound(pe+1,pe+n+1,tmp,FboE())-pe;
84         for(int j=pos;j<=n;++j){
85             if(pe[j].ev>pb[i].ev+d) break;
86             add_edge(pe[j].id,pb[i].id);
87         }
88     }
89     bfs();
90     for(int i=1;i<=n;++i)
91         printf("%d
",dis[i]);
92     return 0;
93 }

USACO 2017 December Contest Gold T1: A Pie for a Pie

题目大意

题目分析