首页 > ACM题库 > HDU-杭电 > hdu 2359 The Final Countdown-贪心-[解题报告]hoj
2014
01-05

hdu 2359 The Final Countdown-贪心-[解题报告]hoj

The Final Countdown

问题描述 :

When Doctor Doom modeled LAI-BACH (the Latverian Aerospace Institute, Bolograd Active Control Headquarters) on Mission Command with
NASA, he perhaps cribbed from the source a bit too closely.

NASA (and therefore LAI-BACH) have a peculiar way of handling countdowns to missions. While the clock may state that it is, say, thirty minutes
until liftoff for a rocket or shuttle, there are built-in holds where the clock is stopped for a set amount of time. For example, there may be a 15-minute
hold when the countdown reaches the 8-minute mark. The end result is that more time passes from the beginning of the countdown to the end than
the numbers on the clock would imply.

LAI-BACH uses a simple "command file" format to manage holds for their countdowns on their computer systems. All commands start with a
positive integer no greater than 1440 (countdowns longer than a day make Doctor Doom angry), followed by a directive. The format of the
commands is as follows:

All conditions are represented by short strings of lowercase letters, no more than 20 characters long; their actual values are not provided in the
command structure, as they are determined by actual conditions during the launch (whether the fuel tanks have been topped off, whether the
Fantastic Four is currently fighting Doctor Doom, and so on), but they are always either true or false and do not change during the course of a single
countdown. A hold time n is a positive integer no more than 60 (minutes), as long delays also irritate Victor.

Given a particular command file, you are to determine both the shortest possible time and the longest possible time that the countdown can run. The
commands may be present in any order, but there will always be one and only one START directive; there will be precisely as much whitespace on
each line as dictated by the format given above. No two commands in a command file will reference the same minute t.

输入:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer L (1 ≤ L ≤ 100) indicating the number of lines in the particular "command file"; and
A series of L lines representing the command file, in the format described above.

输出:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer L (1 ≤ L ≤ 100) indicating the number of lines in the particular "command file"; and
A series of L lines representing the command file, in the format described above.

样例输入:

2
3
30 START
15 HOLD 5
10 HOLD 5 IF fantasticfour
3
75 HOLD 20 IF yellowlightblinks
150 HOLD 30 IF NOT fueled
300 START

样例输出:

35 TO 40
300 TO 350


HOJ 2359/POJ 2393 Yogurt
factory
传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2359

http://poj.org/problem?id=2393

题意:题目叙述比较繁琐,但是题意比较容易理解,就是有个工厂,每周的生产成本不太一样,单位成本分别为Ci,还有一个仓库,单位消耗为每周S,工厂每周需要给客户Yi数量的产品,为最低成本价是多少?
输入:N,S每周的生产成本Ci和数量Yi。
输出:最低成本。
思路:就是每次找到成本最低的方案进行生产,保留上一周的方案单位成本t,然后用t+s和本周成本ci进行比较,取较小的即可。因为方案一旦被淘汰则不会再被启用,这样可以边输入边处理。PS:HOJ竟然在输出的是long
long不能用%I64d。
程序:
#include
<cstdio>
#include
<algorithm>
using
namespace
std;
typedef
long
long
int64;
int
main() {
    int n, s;
    while (scanf(“%d %d”, &n, &s) == 2) {
int64 ans = 0, t;
int
c, y;
for
(int
i = 0; i < n; i++) {
scanf(“%d %d”, &c, &y);
if
(i == 0) {
t = (int64)c;
} else {
t = min(t + s, (int64)c);
}
ans += t * y;
}
printf(“%lld\n”, ans);
    }
    return 0;
}
HOJ 2490/POJ 3069 Saruman’s
Army
传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2490

http://poj.org/problem?id=3069

题意:这道题可以理解成这样,有一个半径为r的圆圈,x轴上有N个点,圆圈必须放在这N个点的某个点上,最少需要多少个圆圈才能将所有的点都用圆圈覆盖到。
输入:N个点的坐标和半径r。
输出:最少需要的圆圈数。
思路:先排序,从小到大,以最小的x为中心,找到距离x
+ r范围内最有的点,再以该点为中心向右,这样找到的是第一个圆圈所能包含的最多的点,以此类推。
程序:
#include
<iostream>
#include
<algorithm>
using
namespace
std;
const
int
MAX = 1024;
int
main() {
    int r, n, x[MAX];
    while (cin >>
r >> n
&&
!(r == -1 && n
== -1)) {
for
(int
i = 0; i < n; i++) {
cin >>
x[i];
}
sort(x, x + n);
int
ans = 0, i = 0;
while
(i < n) {
int s
= x[i];
while
(i < n &&
x[i] <= s + r) {
i++;
}
ans++;
s = x[i - 1];
while
(i < n &&
x[i] <= s + r) {
i++;
}
}
cout <<
ans <<
endl;
    }
    return 0;
}
解题参考:http://blog.sina.com.cn/s/blog_65f3869301011dia.html


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  5. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。