出处： Codeforces
主要算法：贪心+优先队列
难度：4.6
思路分析：
这道题乍一看没有思路……
考虑贪心的做法。首先预处理出每两座相邻的桥之间边界相差的min和max（即题目要求的），存在b数组中。将桥的长度从小到大排序。将b数组按照min从小到大排序。
这样做有什么好处呢？我们枚举每一座桥，然后按顺序选出它适合放置的那些区间。由于这些区间都是适合放这座桥的，所以我们自然要选择差距最小的，也就是max最小的。这其实是一个贪心：让当前这座桥利用的区间尽量小，让别的更长的桥有更大的空间——这就是为什么b数组要排序。
那么具体如何来实现呢？我们可以维护一个优先队列。在这些桥的长度都>=min的情况下，我们需要max最小。因此我们可以用优先队列维护，max最小的作为堆顶。然后每一次都选出第一个区间来安置当前这座桥。如果发现无法安置，那么也就是说在所有适合当前桥的区间都已近用完了，也就无解了。
代码注意点：
变量名不要打错。
Code
/** This Program is written by QiXingZhi **/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
#define int ll
const int N = ;
const int M = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
struct Island{
int l,r;
}a[N];
struct Dist{
int min,max,idx;
friend bool operator < (Dist a, Dist b){
return a.max > b.max;
}
}b[N];
struct Bridge{
int len,idx;
}bri[M];
int n,m,top,cnt;
int ans[N];
priority_queue <Dist> q;
inline bool comp_dist(Dist& a, Dist& b){
if(a.min != b.min) return a.min < b.min;
return a.max < b.max;
}
inline bool comp_bridge(Bridge& a, Bridge& b){
return a.len < b.len;
}
#undef int
int main(){
#define int ll
// freopen(".in","r",stdin);
n = read(), m = read();
for(int i = ; i <= n; ++i){
a[i].l = read();
a[i].r = read();
}
for(int i = ; i <= m; ++i){
bri[i].len = read();
bri[i].idx = i;
}
for(int i = ; i < n; ++i){
b[i].max = a[i+].r - a[i].l;
b[i].min = a[i+].l - a[i].r;
b[i].idx = i;
}
sort(b+,b+n,comp_dist);
sort(bri+,bri+m+,comp_bridge);
int lst = ;
for(int i = ; i <= m; ++i){
if(cnt >= n-) break;
while(lst < n && b[lst].min <= bri[i].len && bri[i].len <= b[lst].max){
q.push(b[lst]);
++lst;
}
if(!q.size()) continue;
Dist tmp = q.top();
q.pop();
if(bri[i].len <= tmp.max){
ans[tmp.idx] = bri[i].idx;
++cnt;
}
else{
printf("No");
return ;
}
}
if(cnt < n-){
printf("No");
return ;
}
printf("Yes\n");
for(int i = ; i < n; ++i){
printf("%lld ", ans[i]);
}
return ;
}