Closing ceremony
题目链接
分类：greedy
1.题目描述
n×m
个座位， 有
n×m
个人，一开始有
k
个人在
(0,0)点上，
l
个人在
(0,m 1)点上，每个人有对应的体力值，体力值即为可以行走的距离（曼哈顿距离），问是否存在一种方案是每个人花费的体力不超过上限，且每个人都有位置坐。
2.解题思路
对于前
k
个人，我们按照体力排序，显然找到一个以距离
(0,m 1)尽可能远为第一关键字，与
(0,0)
尽可能远为第二关键字的位置，那么这个人就应该在这个位置。之后
l
个人放到与
(0,m 1)尽可能远的且没有人的位置，去检测是否存在这种可能就行。
3.AC代码
struct node {
int x, y, z, dis;
friend bool operator< (
const node &aa,
const node &bb) {
return aa.z < bb.z;
}
} p[maxn];
int a[maxn];
priority_queue<node> q;
bool cmp(
const node &x,
const node &y) {
return x.dis < y.dis;
}
int main() {
int n, m, k;
scanf(
"%d%d%d", &n, &m, &k);
rep(i,
1, k +
1)
scanf(
"%d", &a[i]);
int cnt =
0;
sort(a +
1, a + k +
1);
rep(i,
1, n +
1) {
rep(j,
1, m +
1) {
p[++cnt].x = i; p[cnt].y = j;
p[cnt].z = m +
1 - j + i;
p[cnt].dis = i + j;
}
}
sort(p +
1, p + cnt +
1, cmp);
bool ok =
1;
int u =
1;
rep(i,
1, k +
1) {
while(a[i] >= p[u].dis && u <= cnt) {
q.push(p[u]);
u++;
}
if(q.empty()) {
ok =
0;
break;
}
q.pop();
}
if(!ok)
puts(
"NO");
else {
while(u <= cnt) {
q.push(p[u]);
u++;
}
scanf(
"%d", &k);
rep(i,
1, k +
1)
scanf(
"%d", &a[i]);
sort(a +
1, a + k +
1);
per(i,
1, k +
1) {
if(a[i] < q.top().z) {
ok =
0;
break;
}
q.pop();
}
puts(ok ?
"YES" :
"NO");
}
return 0;
}
