Chapter2——基础算法——贪心

1. 题目列表

• POJ1328（二维问题到一维的转换，区间贪心）
• POJ2109
• POJ2586（理解题目，定义贪心策略）

2. POJ1328——Radar Installation

2.1 题目描述

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

<center> image

Figure A Sample Input of Radar Installations</center>

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Sample Input

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

2.2 思路

对于任意一个岛屿，其与x轴相交的交点有0或1或2个，0个特判无解，1个和2个可以认为是Radar的安装范围，先根据几何关系求出每个岛屿的Radar安装范围，将每个范围区间从小到大排序，然后转化问题为区间贪心问题。

问题的本质是，在一系列可能相交的区间中，问怎么样放置点，使得每个区间至少存在一个点并且要求所放的点数最少。

  可以使用贪心算法求解，维护右端点。
  1. 从左起的第一个区间A开始遍历，在其右段点放置一个点。
  2.  若下一个区间B的左端点大于右端点，
      说明A与B无交集，则在更新右端点为B的右端点，总放置的端点数 + 1
  3. 若B的左端点小于等于右端点，说明A与B相交，此时进一步讨论
        (1). 若B的右端点小于等于右端点，则说明B在A内，则更新右端点为B的右端点
        (2). 若B的右端点大于A的右端点，则说明B不在A内，则右端点保持不变 

2.3 代码

#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;
struct Coor{
    int x;
    int y;
} coor[1010];
struct Range{
    double l,r;
} range[1010];

bool visited[1010];

void caculateRange(int n, int d){
    for (int i = 0; i < n; i++){
        range[i].l = coor[i].x - sqrt(d * d - coor[i].y * coor[i].y);
        range[i].r = coor[i].x + sqrt(d * d - coor[i].y * coor[i].y);
    }
} 

int solve(int n){
    /* 问题的本质是，在一系列可能相交的区间中，问怎么样放置点，使得每个区间至少存在一个点
     并且要求所放的点数最少。
      
      可以使用贪心算法求解，维护右端点。
      1. 从左起的第一个区间A开始遍历，在其右段点放置一个点。
      2.  若下一个区间B的左端点大于右端点，
          说明A与B无交集，则在更新右端点为B的右端点，总放置的端点数 + 1
      3. 若B的左端点小于等于右端点，说明A与B相交，此时进一步讨论
            (1). 若B的右端点小于等于右端点，则说明B在A内，则更新右端点为B的右端点
            (2). 若B的右端点大于A的右端点，则说明B不在A内，则右端点保持不变 
    
    */   
    int right = range[0].r, cnt = 1;
    for (int i = 1; i < n; i++){
        // 区间无交集
        if (range[i].l > right){
            cnt ++;
            right = range[i].r;
        } else if (range[i].r <= right){ // 内部 
            right = range[i].r;
        }else{
            
        }
    } 
    return cnt;
} 

int cmp(Range r1, Range r2){
    if (r1.l == r2.l)
        return r1.r < r2.r;
    return r1.l < r2.l;
}

int main(){
    int n,d;
    scanf("%d%d",&n,&d);
    for(int T = 1; n != 0 && d!= 0; T++, scanf("%d%d",&n,&d)){ 
        bool flag = false;
        for (int i = 0; i < n; i++){
            scanf("%d%d",&coor[i].x, &coor[i].y);
            if (coor[i].y > d || coor[i].y < 0 || d < 0) // 如果存在任何雷达都覆盖不到的点 或者小岛不在海上 
                flag = true;
        }
        getchar();
        getchar();
        if (flag){
            printf("Case %d: -1\n", T);
            continue;
        }
        
        // 这个问题的本质是对于任意多个区间，使用最少的点来占据所有的区间
        
        caculateRange(n, d); // 计算所有的区间
        sort(range, range + n, cmp); //从小到大排序 
        int res = solve(n);
        printf("Case %d: %d\n", T, res);
    }
}

3. POJ2109——Power of Cryptography

3.1 问题描述

Description

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers among these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be only of theoretical interest.
This problem involves the efficient computation of integer roots of numbers.
Given an integer n>=1 and an integer p>= 1 you have to write a program that determines the n th positive root of p. In this problem, given such integers n and p, p will always be of the form k to the nth. power, for an integer k (this integer is what your program must find).
Input

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<=n<= 200, 1<=p<10101 and there exists an integer k, 1<=k<=109 such that kn = p.
Output

For each integer pair n and p the value k should be printed, i.e., the number k such that k n =p.

Sample Input

2 16
3 27
7 4357186184021382204544

Sample Output

4
3
1234

3.2 思路

给定，求解，由于p的数据范围在101位，所以需要使用高精度算法求解。但本题可以直接使用math的pow函数求根，即可求解出来。

3.3 代码

#include <cstdio>
#include <cmath>
#include <iostream>

using namespace std;

int main(){
    int n;
    double p; // double类型虽然能表示10^(-307)~ 10^(308)，但有效精度只有16位 
    while (scanf("%d%lf",&n,&p) != EOF){
        cout<<pow(p, 1.0 / n)<<endl; // pow函数的开方可避免高精度问题 
    }
    return 0;
}

注意：

• double可以表示307位数，但只能拥有16位的精度，超过16位后面全用0替代
• power也可以对丢失精度的double运算

4. POJ2109——Y2K Accounting Bug

4.1 题目描述

Description

Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.

Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.
Input

Input is a sequence of lines, each containing two positive integers s and d.
Output

For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.

Sample Input

59 237
375 743
200000 849694
2500000 8000000

Sample Output

116
28
300612
Deficit

4.2 解决思路

本题重点在于读懂题目。原问题给出每个月固定的s和d值，并限定一年中连续5个月必然亏损，因此有8个连续的5个月的报表为亏损。
因此，分情况讨论5个月中剩余和亏损的情况，贪心：并以年总剩余量最大目标，分为以下5个优先级，对于不同的输入判断属于哪个优先级：
P1. ssssd,ssssd,ss, if d > 4s 优先级别最高
P2. sssdd,sssdd,ss, if 2d > 3s
P3. ssddd,ssddd,ss, if 3d > 2s
P4. sdddd,sdddd,sd, if 4d > s
P5. ddddd,ddddd,dd, else

4.3 代码

#include <cstdio>

int main(){
    int s,d;
    // 所有可能的5中情况，并且从上到下优先s个数最多，d个数最少 
    // ssssd,ssssd,ss, if d > 4s   优先级别最高 
    // sssdd,sssdd,ss, if 2d > 3s   
    // ssddd,ssddd,ss, if 3d > 2s
    // sdddd,sdddd,sd, if 4d > s
    // ddddd,ddddd,dd, else
    while (scanf("%d%d",&s,&d) != EOF){
        int res = 0;
        if (d > 4 * s){
            res = 10 * s - 2 * d;
        }else if(2 * d > 3 * s){
            res = 8 * s - 4 * d;
        } else if (3 * d > 2 * s){
            res = 6 * s - 6 * d;
        }else if (4 * d > s){
            res = 3 * s - 9 * d;
        }
        else res = -1;
        if (res > 0){
            printf("%d\n",res);
        }else{
            printf("Deficit\n");
        }
    }
}

5. 总结

贪心问题往往是一个求最大值、最小值、最优方案的问题，准确找到贪心目标，根据题意求解，没有固定的模板，最重要的是读懂和转化问题。