Uva 10382: Watering Grass

tags: 貪心法 區間覆蓋

一個長為

$l$, 寬為

$w$ 的田地有

$n$ 個灑水器, 給定每個灑水器的位置, 以及其噴灑半徑

$r$, 試計算出能噴到整個田地灑水器的最小數量, 若無法完全覆蓋，則輸出

$-1$，反之輸出最小數量。

Source: 題目傳送門

---

Original

題目敘述

$n$ sprinklers are installed in a horizontal strip of grass

$l$ meters long and

$w$ meters wide.

Each sprinkler is installed at the horizontal center line of the strip.

For each sprinkler we are given its position as the distance from the left end of the center line and its radius of operation.

Question

What is the minimim number of sprinklers to turn on in order to water the entire strip of grass?

Input format

Input consists of a number of cases.

The first line for each case contains integer numbers

$n$,

$l$ and

$w$ with

$n\le 10000$.

The next

$n$ lines contain two integers giving the position of a sprinkler and its radius of operation. (The picture above illustrates the first case from the sample input.)

Output format

For each test case output the minimum number of sprinklers needed to water the entire strip of grass. If it is impossible to water the entire strip output ‘-1’.

Sample Input

​​​​8 20 2
​​​​5 3
​​​​4 1
​​​​1 2
​​​​7 2
​​​​10 2
​​​​13 3
​​​​16 2
​​​​19 4
​​​​3 10 1
​​​​3 5
​​​​9 3
​​​​6 1
​​​​3 10 1
​​​​5 3
​​​​1 1
​​​​9 1

Sample Output

​​​​6
​​​​2
​​​​-1

---

概念

• 貪心
• 區間覆蓋

---

主要思路

• 首先，灑水器一律擺放至田地中央
  $\frac{w}{2}$ 處，透過畢氏定理由
  $\frac{w}{2}$ 與
  $r$ 算出其可擴展到的左、右交點，如此便變成區間覆蓋問題

• 由二維題目轉變為單維，每個灑水器都有左、右可擴展到的交點位置，如上圖紅圈處標示，即代表在這區段之內的草坪皆可覆蓋到
• 接著依據左交點位置排序，而貪心在於每次查找時下一個必須涵蓋在當前的右交點內(其左交點必須在內)，並儘可能的往右覆蓋
• 當
  $r<\frac{w}{2}$ 時，該灑水器要捨棄掉(沒辦法完全覆蓋草坪的灑水器)，此外若最左沒有覆蓋到0，或最右沒有覆蓋到
  $l$，代表草坪無法覆蓋完全，則輸出
  $-1$。

---

程式碼

#include <iostream>
#include <cmath>

using namespace std;

typedef struct S_pair
{
    double left;
    double right;
}s_pair;

//qsort compare function
int32_t compare(const void *a, const void *b)
{
    if ((((s_pair *)a)->left) > (((s_pair *)b)->left)) 
        return 1;
        
    return 0;
}

int main()
{

    int32_t n = 0, l = 0, w = 0;
    while (cin >> n >> l >> w)
    {
        s_pair arr[n];
        int32_t ans = 0;
        for (int32_t i = 0 ; i < n ; i ++)
        {
            int32_t pos = 0, r = 0;
            double len = 0;
            cin >> pos >> r;

            if (r < (double)(w/2))
            {
                //失效的灑水器往不可能的地方擺即可
                arr[i].left = l + 5000;
                arr[i].right= l + 5000;
            }
            else
            {
                len = sqrt(1.0 * r * r - (w/2.0)*(w/2.0));
                arr[i].left = pos - len;
                arr[i].right= pos + len;
            }

            //若當個灑水器可覆蓋全部則ans=1
            if (pos-len <= 0 && pos+len >= l) ans = 1;
        }

        if (ans) cout << "1" << endl;
        else
        {
            ans = 1;
           
            //依左交點排序 
            qsort(arr, n, sizeof(s_pair), compare);

            for (int32_t i = 0 ; i < n ; i++)
            {
                if (arr[i].right >= l) break;

                int32_t right_num = -1;

                for (int32_t j = i+1; j < n ; j++)
                {
                    int32_t temp = (arr[i].right >= arr[j].left);
                    if ((right_num == -1)&& temp ==1)
                    {
                        right_num = j;
                    }
                    else if (temp==1 && (arr[j].right > arr[right_num].right))
                        right_num = j;
                }

                i = right_num-1;
                ans +=1;
                if (right_num != -1 && arr[right_num].right >= l) break;

                //覆蓋失敗
                if (right_num == -1)
                {
                    ans = 0;
                    break;
                }
            }
            //覆蓋成功 
            if (ans!=0 && arr[0].left <= 0) cout << ans << endl;
            else cout << "-1" << endl;
        }
    }
    return 0;
}