1016 - Brush (II)
You can assume that the rope is sufficiently large. Now Samee wants to clean the room with minimum number of moves. Since he already had a contest, his head is messy. So, help him.After the long contest, Samee returned home and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found a brush in his room which has width w. Dusts are defined as 2D points. And since they are scattered everywhere, Samee is a bit confused what to do. So, he attached a rope with the brush such that it can be moved horizontally (in X axis) with the help of the rope but in straight line. He places it anywhere and moves it. For example, the y co-ordinate of the bottom part of the brush is 2 and its width is 3, so the y coordinate of the upper side of the brush will be 5. And if the brush is moved, all dusts whose y co-ordinates are between 2 and 5 (inclusive) will be cleaned. After cleaning all the dusts in that part, Samee places the brush in another place and uses the same procedure. He defined a move as placing the brush in a place and cleaning all the dusts in the horizontal zone of the brush.
Input
Input starts with an integer T (≤ 15), denoting the number of test cases.
Each case starts with a blank line. The next line contains two integers N (1 ≤ N ≤ 50000) and w (1 ≤ w ≤ 10000), means that there are N dust points. Each of the next N lines will contain two integers: xi yi, denoting coordinates of the dusts. You can assume that (-109 ≤ xi, yi ≤ 109) and all points are distinct.
Output
For each case print the case number and the minimum number of moves.
| Sample Input | Output for Sample Input |
| 23 20 0
20 2 30 2
3 1 0 0 20 2 30 2 |
Case 1: 1Case 2: 2 |
Note
Data set is huge, so use faster I/O methods.
题目类型：贪心
算法分析：由于刷子可以水平扫过所有的长度，所以点的横坐标没有用，只需考虑纵坐标，显然这是一个区间覆盖点问题，直接贪心选择即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 66666; int ans[maxn]; int main() { // freopen ("aaa.txt", "r", stdin); int t, flag = 1; scanf ("%d", &t); while (t--) { printf ("Case %d: ", flag++); int n, w; scanf ("%d%d", &n, &w); int temp, i; for (i = 0; i < n; i++) scanf ("%d%d", &temp, &ans[i]); sort (ans, ans + n); int sum = 1, p = ans[0]; for (i = 1; i < n; i++) { if (ans[i] > w + p) { sum++; p = ans[i]; } } printf ("%d\n", sum); } return 0; } |
- « 上一篇：lightoj1014
- lightoj1019：下一篇 »