第一题：涂面包
描述：
你要在面包片上涂layer_count层，做成山莓酱面包。考虑到每次涂酱，你只能最多涂upper_limit层，要求算出最少的涂酱次数。
分析：
要求最少的涂酱次数，只要每次涂尽可能多的山莓酱就好了。这是很典型的贪心思路。
代码：
int ToastXRaspberry::apply( int upper_limit, int layer_count) {
if (layer_count % upper_limit == 0){
return layer_count / upper_limit;
}
return layer_count / upper_limit + 1
}
第二题：烤面包
描述：
对于每一种类的面包，都有一个烧烤时间X。如果面包恰好被烤了X分钟，则称为好面包。少于X，则是不熟的；多于X就烤焦了。面包师现在烤了一些面包。由于他并不知道每种面包的确切烧烤时间，所以每个面包要不是不熟就是烤焦了。他唯一记得的是，每种面包都被烤不熟或烤焦了。现在你已知不熟面包和烤焦面包被烤的确切时间，给出至少有几种面包类被使用了。
分析：
题目比较难理解。简单的解释就是说，如果有一种面包，面包师把它烤不熟了，则面包师也把它烤焦了。因此，如果x1为最小烤焦时间，必大于最小的不熟时间y1，否则只有一种面包被烤焦了，它却没有被烤不熟，矛盾。同样的，如果x2为最大的烤焦时间，比大于最大的烤不熟时间y2，否则对那个烤不熟的面包来说，跟它同种的面包里没有被烤焦，矛盾。如果上面两种情况都不符合，则至少有一种面包被用来烤了。如果x1大于y2，则面包只有一种。否则，烧烤时间t1小于x1同时大于y1的面包，在比x1大的烤焦时间里面同样被烤焦。但由于t1小于y2，则至少还有另一种面包被烤了。由于x2大于y2，t2只要小于x2同时大于y2就可以了。这样，比y2小的所有时间，该种面包都不能烤熟。这样，可能被烤的面包种类其实最多只有两种。
代码：
int ToastXToast::bake( vector < int > undertoasted, vector < int > overtoasted) {
sort(undertoasted.begin(), undertoasted.end());
sort(overtoasted.begin(), overtoasted.end());
if (undertoasted[undertoasted.size() - 1] <= overtoasted[0]){
return 1;
}
else if (undertoasted[0] >= overtoasted[0]
|| undertoasted[undertoasted.size() - 1] >= overtoasted[overtoasted.size() - 1]){
return -1;
}
else {
return 2;
}
}
第三题：村村通公路
描述：
在一个星球上，有很多个城市和农村。农村都很孤立，没有跟城市连接起来。你现在要修建公路把农村跟城市连接起来。如果一个村已经跟城市连接起来，则其他村可以间接通过这个村和城市连接。给定所有城市和村庄的坐标，要求计算所需修建的路的最小长度。两个点之间的距离是欧氏距离。
分析：
如果用A表示城市，B表示已经跟城市连接的村庄，C表示还没跟城市连接的村庄。对C中的每个村落来说其当前要修建的公路的最少长度要么是到A中的某个城市，要么是到B中的某个村落。这时应该先建一条路把A或B跟C中距离最近的点x联通起来。如果先建到C中别的点y，则后面x还要通过C中的点z连入公路网，这个距离要比直接把x和公路网连起来要远得多。这是一个很明显的贪心性质。这意味着，我们每一次只要从C中选一个距离公路网最近的点x，添加到B中就可以了。当C中所有的点都被加入公路网，则计算就结束了，所获得的公路网就是最短的。
代码：
double KingdomXCitiesandVillagesAnother::determineLength( vector < int > cityX,
vector < int > cityY,
vector < int > villageX,
vector < int > villageY) {
int cities = cityX.size();
int villages = villageX.size();
vector < double > distance(villages);
vector < bool > flag(villages, false );
int count = 0;
double sum = 0;
for ( int i = 0;i < cities;i++){
for ( int j = 0; j < villages; ++j) {
double d = DIS(( double )cityX[i], ( double )cityY[i], ( double )villageX[j], ( double )villageY[j]);
if (i){
if (distance[j] > d){
distance[j] = d;
}
}
else {
distance[j] = d;
}
}
}
do {
int k = -1;
double min = -1;
for ( int i = 0;i < villages;i++){
if (!flag[i]){
if (k <= -1){
k = i;
min = distance[i];
}
else {
if (distance[i] < min){
k = i;
min = distance[i];
}
}
}
}
flag[k] = true ;
count++;
sum += min;
for ( int i = 0;i < villages;i++){
if (!flag[i]){
double d = DIS(( double )villageX[i], ( double )villageY[i], ( double )villageX[k], ( double )villageY[k]);
if (d < distance[i]){
distance[i] = d;
}
}
}
} while (count < villages);
return sum;
}
小结
这次的题目以第一和第三题最容易，第二道题只要理解题目，找到几个关键点就可以了。很悲剧的是，比赛的时候卡在第二道题了，自己把英文的题目看了很多遍，看明白的时候还剩下二十分钟了。二十分钟里面，自己又没发现最大烤焦时间一定要大于最大烤不熟时间，结果只写出了返回-1和1的代码，差了一个return 2。
想来每次topcoder比赛，光是看题目就已经花了半个小时，75分钟就只剩下45分了。在45分钟里需要发现题目里面蕴含的条件，在这个基础上设计有效的算法，对我来说还是挺难的。咳，还是要提高英文阅读能力，平时多练练啊。
