【计算机考研机试指南】第七章 贪心策略:Case of Fuigitive
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <queue>using namespace std;const int MAXN = 200001;struct Island{long long left;//岛屿左端点
·
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 200001;
struct Island{
long long left; //岛屿左端点
long long right; //岛屿右端点
};
struct Bridge{
long long length; //桥长度
long long index; //桥编号
};
struct Interval{
long long minimum; //区间最小
long long maxmum; //区间最大
long long index; //区间编号
bool operator< (Interval x) const{
return maxmum > x.maxmum;
}
};
bool IntervalCompare(Interval x, Interval y){
if(x.minimum == y.minimum){
return x.maxmum < y.maxmum;
}else{
return x.minimum < y.minimum;
}
}
bool BridgeCompare(Bridge x, Bridge y){
return x.length < y.length;
}
Island island[MAXN];
Bridge bridge[MAXN];
Interval interval[MAXN];
long long answer[MAXN];
bool Solve(int n, int m){
priority_queue<Interval> myQueue;
int position = 0; //当前区间下标
int number = 0; //搭建桥的数目
for(int i = 0; i < m; i++){
while(myQueue.top().maxmum < bridge[i].length && !myQueue.empty()){
myQueue.pop(); //当前区间不可搭建
}
while(position < n-1 &&
interval[position].minimum <= bridge[i].length &&
interval[position].maxmum >= bridge[i].length){
myQueue.push(interval[position]);
position++;
}
if(!myQueue.empty()){
Interval current = myQueue.top();
myQueue.pop();
answer[current.index] = bridge[i].index;
number++;
}
}
return number == n - 1; //判断桥数目和区间数目是否相等
}
int main(int argc, char** argv) {
int n, m;
while(scanf("%d %d", &n, &m) != EOF){
memset(island, 0, sizeof(island));
memset(bridge, 0, sizeof(bridge));
memset(interval, 0, sizeof(interval));
memset(answer, 0, sizeof(answer));
for(int i = 0; i < n; i++){
scanf("%lld %lld", &island[i].left, &island[i].right);
}
for(int i = 0; i < m; i++){
scanf("%lld", &bridge[i].length);
bridge[i].index = i + 1;
}
for(int i = 0; i < n-1; i++){
interval[i].minimum = island[i + 1].left - island[i].right;
interval[i].maxmum = island[i + 1].right - island[i].left;
interval[i].index = i;
}
sort(interval, interval + n - 1, IntervalCompare);
sort(bridge, bridge + m, BridgeCompare);
cout << "FLAG" << endl;
if(Solve(n, m)){
printf("YES\n");
for(int i = 0; i < n - 1; i++){
printf("%lld\n", answer[i]);
}
}else{
printf("NO\n");
}
cout << "FLAG" << endl;
}
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)