1689: [Usaco2005 Open] Muddy roads 泥泞的路
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 229 Solved: 166
[Submit][Status]
Description
Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools. Farmer John has a collection
of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely. Given the mud pools, help FJ figure out the minimum number of
planks he needs in order to completely cover all the mud pools.
Input
* Line 1: Two space-separated integers: N and L * Lines 2..N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the start and end points of
a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap.
Output
* Line 1: The miminum number of planks FJ needs to use.
Sample Input
1 6
13 17
8 12
Sample Output
贪心经典题,注意细节和代码实现
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive ************************************************/ ///////////////////////////////////////////////// #define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) ///////////////////////////////////////////////// int n,l; struct Orz{int s,e;}dat[10010]; ///////////////////////////////////////////////// bool cmp(const Orz &a,const Orz &b){return a.s<b.s;} ///////////////////////////////////////////////// void input() { scanf("%d%d",&n,&l); rep(i,1,n) scanf("%d%d",&dat[i].s,&dat[i].e); } void solve() { ///////////////////init/////////////////// int ans=0; int last=-999999; ////////////////calculate//////////////// sort(&dat[1],&dat[n+1],cmp); rep(i,1,n) { if(last+l>=dat[i].e) continue; last=max(last+l,dat[i].s); ans++; while(dat[i].e>last+l)last+=l,ans++; } /////////////////output///////////////// printf("%d\n",ans); } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif input(); solve(); #ifdef _TEST for(;;); #endif return 0; }