poj-1328的解题思路是什么？

本文共计719个文字，预计阅读时间需要3分钟。

当然可以，请提供您希望改写的原文，我将为您进行修改。

#include <stdio.h> #include <math.h> #include <malloc.h> struct location { double x; double y; bool processed; }; struct locationValidXRange { double begin; double end; }; bool locationCanReach(location * islandLocation, int islandNum, double radarDistance) { for (int i = 0; i < islandNum; i++) { if (islandLocation[i].y > radarDistance) { return false; } } return true; } void swapLoctaionRange(locationValidXRange * locationRange1, locationValidXRange * locationRange2) { double begin = locationRange1->begin; double end = locationRange1->end; // bool processed = location1->processed; locationRange1->begin = locationRange2->begin; locationRange1->end = locationRange2->end; // location1->processed = location2->processed; locationRange2->begin = begin; locationRange2->end = end; // location2->processed = processed; } void sortLocationsRangeAsBeginAscend(locationValidXRange * islandLocationRange, int islandNum) { for (int i = 0; i < islandNum - 1; i++) { bool exchanged = false; for (int j = 0; j <= (islandNum - i) -1 - 1; j++) { if (islandLocationRange[j].begin > islandLocationRange[j+1].begin) { swapLoctaionRange(islandLocationRange + j, islandLocationRange + j + 1); exchanged = true; } } if (!exchanged) { return; } } } double getMaxXForLocation(location * islandLocation, double radarDistance) { double sqrtRes = sqrt((double)radarDistance*radarDistance - islandLocation->y * islandLocation->y); return sqrtRes + islandLocation->x; } void getValidXRangeForLocation(location * islandLocation, double radarDistance, double *begin, double *end) { double sqrtRes = sqrt((double)radarDistance*radarDistance - islandLocation->y * islandLocation->y); *begin = ((double)islandLocation->x - sqrtRes); *end = ((double)islandLocation->x + sqrtRes); } int getRadarMinNum(locationValidXRange * islandLocationRanges, int rangeNum) { int radarNum = 1; double begin = islandLocationRanges[0].begin; double end = islandLocationRanges[0].end; for(int i = 1; i < rangeNum ;i++) { if (islandLocationRanges[i].begin <= end) { begin = islandLocationRanges[i].begin; end = end > islandLocationRanges[i].end ? islandLocationRanges[i].end : end; } else { radarNum++; begin = islandLocationRanges[i].begin; end = islandLocationRanges[i].end; } } return radarNum; } void printLocationRanges(locationValidXRange * islandLocationRanges, int islandNum) { printf("=========================================\n"); for (int i = 0; i < islandNum ; i++) { printf("%lf %lf\n", (islandLocationRanges+i)->begin, (islandLocationRanges+i)->end); } printf("=========================================\n"); } int main() { int caseId = 1; while(1) { int islandNum; double radarDistance; scanf("%d %lf\n", &islandNum, &radarDistance); if (islandNum == 0 && radarDistance == 0) { return 0; } location * islandLocations = (location *) malloc(islandNum * sizeof(location)); locationValidXRange * locationValidXRanges = (locationValidXRange *) malloc(islandNum * sizeof(locationValidXRange)); for (int i = 0; i < islandNum ; i++) { scanf("%lf %lf", &(islandLocations[i].x), &(islandLocations[i].y)); getValidXRangeForLocation(islandLocations + i, radarDistance, &(locationValidXRanges[i].begin), &(locationValidXRanges[i].end)); islandLocations[i].processed = false; } if (!locationCanReach(islandLocations, islandNum, radarDistance)) { printf("Case %d: -1\n", caseId); caseId++; continue; } sortLocationsRangeAsBeginAscend(locationValidXRanges, islandNum); // printLocationRanges(locationValidXRanges, islandNum); printf("Case %d: %d\n", caseId, getRadarMinNum(locationValidXRanges, islandNum)); free((void*)islandLocations); islandLocations = NULL; caseId++; } }

贪心法： 每次的radar都以能覆盖最多的小岛为选择准则（证明可以用算法导论的替代法则： 假如当前的一个最优解里不是当前选择的radar位置，

那么置换成贪心法的选择，则结果只会更好，不会更差。）

先用radar的半径求出所有小岛的x range（radar在此range可以覆盖小岛）， 然后以range begin做升序排序，最后便利一边range数组，

每次更新当前的有效range，如果当前range不能覆盖此小岛，则radar数量+1， range刷新为此小岛的range。

一开始用贪心法没找对对象，用每次能覆盖第一的小岛的x坐标最大的radar作为标准，是不对。

贪心和动规难就在于找出这种最优子结构。

注意：

1. 小岛的坐标， radar的坐标， 半径都要用double，不然WA。

2. 一开始接收输入时，就可以判断小岛的y坐标，超过了radar半径，直接返回-1.

3. double 用 %lf。

4 struct封装很方便。 感受了封装性的内涵.

5. malloc free -> malloc.h