Gym101606E Education

题目链接

题意：
有n个系要搬家（系的属性：人数；人数是一个整体，不可分割，本系的不能够和别的系共享一个建筑），有m个建筑可以选择（建筑的属性：可容纳的人数；一年的租金），让我们选择花费最少的租房方案：依次输出对应的系（从第1个系开始）选择了哪个建筑（编号从1开始）。
如果租不到合适的房子（住不下），输出”impossible”。若有多种情况满足条件，输出任意一种。

做法：
贪心，让人数最多的系优先选择价格最低的建筑。

反省：
1.不能用map映射房子的容量<–>房子的编号，房子的容量可以相同。
2.系人数sort()，题目也没有说就是按升序排列的。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MIN 0x3f3f3f3f
typedef
struct {
// 建筑
int num;
// 容量
int price;
// 价格
int id;
// 编号
}House;
typedef
struct {
// 系
int pep;
// 人数
int id;
// 编号
int ans;
// 选择的建筑的编号
}Depart;
House a[5005];
Depart b[5005];
int f[5005];
// 标记建筑是否被选择
bool
// 建筑按价格升序排列
cmp(House a, House b) {
return a.price < b.price;
}
bool
// 系按人数降序排列
cmpa(Depart a, Depart b) {
return a.pep > b.pep;
}
bool
// 系按编号升序排列
cmpb(Depart a, Depart b) {
return a.id < b.id;
}
int
main() {
int n, m, i, j, flag, cmin, noans;
while( scanf("%d %d", &n, &m) != EOF ) {
for( i = 0; i < n; i++ ) {
scanf("%d", &b[i].pep);
b[i].id = i;
}
for( i = 0; i < m; i++ ) {
scanf("%d", &a[i].num);
a[i].id = i + 1;
}
for( i = 0; i < m; i++ ) {
scanf("%d", &a[i].price);
}
sort(b, b + n, cmpa);
sort(a, a + m, cmp);
memset(f, 0, sizeof(f));
//
for( i = 0; i < n; i++ ) {
// 人数最多的系优先选择价格最低的建筑
flag = -1;
cmin = MIN;
for( j = 0; j < m; j++ ) {
if( a[j].num >= b[i].pep && a[j].price < cmin && f[a[j].id] == 0 ) {
// 住得下，价格更低，没有被选，选择
cmin = a[j].price;
flag = a[j].id;
}
}
b[i].ans = flag;
if( flag != -1 ) {
//
f[flag] = 1;
}
}
noans = 0;
for( i = 0; i < n; i++ ) {
if( b[i].ans == -1 ) {
// 没有选到合适的建筑标记为-1
noans = 1;
break;
}
}
if( noans == 1 ) {
printf("impossible");
}
else {
sort(b, b + n, cmpb);
for( i = 0; i < n; i++ ) {
if( i != 0 ) {
printf(" ");
}
printf("%d", b[i].ans);
}
}
printf("n");
}
return 0;
}

最后

以上就是无私大神为你收集整理的Gym101606E Education的全部内容，希望文章能够帮你解决Gym101606E Education所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。