这层楼沿着走廊南北向的两边各有200个房间。最近，公司要做一次装修，需要在各个办公室之间搬运办公桌。 由于走廊狭窄，办公桌都很大，走廊里一次只能通过一张办公桌。必须制定计划提高搬运效率。 经理制定如下计划：一张办公桌从一个房间移到另一个房间最多用十分钟。当从房间i移动一张办公桌到房间j，两个办公室之间的走廊都会被占用。所以，每10分钟内，只要不是同一段走廊，都可以在房间之间移动办公桌。 输入 输入数据有T组测试例，在第一行给出测试例个数T。 每个测试例的第一行是一个整数N（1≤N≤200)，表示要搬运办公桌的次数。接下来N行，每行两个正整数s和t，表示一张桌子，是从房间号码s移到到房间号码t。 输出 每组输入都有一行输出数据，为一整数T，表示完成任务所花费的最小时间。 在经理给出的说明表格中，已经明确地描述了算法： （从房间30到50）和（从房间60到90）是允许的，因为没有占用公共的走廊； （从房间20到40）和（从房间31到80）是不允许的，因为要占用公共的走廊。 我们将每个房间之间的走廊作为一个统计单位，当所有的办公桌都搬运完成之后，看看这段走廊到底需要占用多少次？然后统计所有的走廊被占用的最大值max，这个值就是要单独安排的搬运次数，乘以10就是总的搬运时间。 int i, j; int move[200]; int N; //搬运次数 int from, to; //每次搬运的起点和终点 scanf("%d", &N); memset(move, 0, sizeof(move)); for(i = 0; i < N; i++){ scanf("%d%d", &from, &to); from = (from - 1)/2; //将房间号映射为走廊号。走廊数组下标从0开始 to = (to - 1)/2; //确保from<to，C++使用：swap(from, to) if(from > to) { int temp = from; from = to; to = temp; } //占用走廊情况 for(j = from; j <= to; j++) move[j]++; } 所有的走廊被占用的最大值 int max = 0; for(i = 0; i < 200; i++) if(move[i] > max) max = move[i]; printf("%d\n", max * 10);
算法5.19选择鱼最多的湖钓鱼的贪心算法实现 //从湖1起到湖pos止，花费时间time（不含路程）的钓鱼计划 void greedy(int pos, int time) { if (time <= 0) return; //时间已经用完 int i, j; int fish[MAXN]; //每个湖能钓到鱼的数量 int p[MAXN]; int t = 0; for (i = 1; i <= pos; ++i) fish[i] = f[i]; memset(p, 0, sizeof§); …… } //在时间time内，选择鱼最多的湖钓鱼；如果鱼都没有了，就把时间放在湖1上 for (i = 0; i < time; ++i){ int max = 0; //鱼最多的湖中，鱼的数量 int id = -1; //鱼最多的湖的编号 //查找鱼最多的湖中，鱼的数量和湖的编号 for (j = 1; j <= pos; ++j) if (fish[j] > max){ max = fish[j]; id = j; } if (id != -1) //找到了，进行钓鱼处理 { ++p[id]; fish[id] -= d[id]; t += max; } //没有找到（从湖1起到湖pos全部钓完了），就把时间放在湖1上 else ++p[1]; } //处理最优方案 if (t > best) { best = t; //最优值 memset(plan, 0, sizeof(plan)); for (i = 1; i <= pos; ++i) //最优解 plan[i] = p[i]; }输出钓鱼计划时，再把5乘回去，就变成实际的钓鱼时间（分钟）： for (i=0; i<n-1; ++i) printf("%d, “, plan[i] * 5); printf(”%d\n", plan[n-1] * 5);
