这个题很显然，可以转换成这个问题：有n-1个区间，m个数，每个数最多只能用一次，第i个数只要能被第j个区间包含，那么这个数就可以放入这个区间内。求出，当所有区间里都恰有一个数时的情况。我们把所有区间按照下限升序排序，所有数升序排序之后分治即可。分治过程，维护一个元素为区间的小堆，堆顶是上限最小的区间。考虑第i个数，把所有能够包含它的区间都丢到堆中，然后从堆中丢一个区间出来，若这个区间可以包含这个数，那么记录下来，否则无解，结束程序。为什么此时无解呢？因为很显然后面的数都不小于这个数，所有后面的数也将无法被这个区间包含，那么这个区间找不到与之匹配的数，故无解。
为什么把上限最小的区间弹出优先考虑呢？因为在有解的情况下，对于第i个数而言，，堆中所有区间都可以包含这个数，且区间下限都会被第j(j>i)个数包含，所以现在只需要考虑区间上限这一个因素，考虑贪心的原则，很显然要优先把上限最小的区间先处理掉。
#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<iostream>#include<algorithm>#include<bitset>#include<climits>#include<list>#include<iomanip>#include<stack>#include<set>using namespace std;typedef long long ll;struct Island{ll l,r;int no;bool operator <(Island one)const{return r>one.r;}}island[int(2e5)+10];bool cmp(Island one,Island two){return one.l<two.l;}struct Bridge{ll len;int no;}bridge[int(2e5)+10];bool cmp1(Bridge one,Bridge two){return one.len<two.len;}priority_queue<Island>qq;int ans[int(2e5)+10];int main(){int n,m;cin>>n>>m;ll pl,pr;for(int i=0;i<n;i++){ll l,r;cin>>l>>r;if(i>0){island[i-1].l=l-pr;island[i-1].r=r-pl;island[i-1].no=i-1;}pl=l;pr=r;}sort(island,island+n-1,cmp);for(int i=0;i<m;i++){cin>>bridge[i].len;bridge[i].no=i;}sort(bridge,bridge+m,cmp1);int sum=0;for(int i=0,j=0;i<m;i++){while(j<n-1&&island[j].l<=bridge[i].len&&bridge[i].len<=island[j].r)qq.push(island[j++]);if(qq.empty())continue;Island t=qq.top();qq.pop();if(bridge[i].len>t.r){puts("No");return 0;}ans[t.no]=bridge[i].no;sum++;}if(sum<n-1){puts("No");return 0;}puts("Yes");for(int i=0;i<n-1;i++){if(i)cout<<" ";cout<<ans[i]+1;}}
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.
The only dry land there is an archipelago ofnnarrow islands located in a row. For more comfort let’s represent them as non-intersecting segments on a straight line: islandihas coordinates[li,ri], besides,ri<li+1for1≤i≤n-1.
To reach the goal, Andrewid needs to place a bridge between each pair ofadjacentislands. A bridge of lengthacan be placed between thei-th and the(i+1)-th islads, if there are such coordinates ofxandy, thatli≤x≤ri,li+1≤y≤ri+1andy-x=a.
The detective was supplied withmbridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands.
Input
The first line contains integersn(2≤n≤2·105) andm(1≤m≤2·105) — the number of islands and bridges.
Nextnlines each contain two integersliandri(1≤li≤ri≤1018) — the coordinates of the island endpoints.
The last line containsmintegernumbersa1,a2,…,am(1≤ai≤1018) — the lengths of the bridges that Andrewid got.
Output
If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line"No"(without the quotes), otherwise print in the first line"Yes"(without the quotes), and in the second line printn-1numbersb1,b2,…,bn-1, which mean that between islandsiandi+1there must be used a bridge numberbi.
离开你的那一天开始，左心房渐渐停止跳动…
