poj3069 Saruman's Army（贪心）

弄清楚一点，第一个stone的位置，考虑左右两边都要覆盖R，所以一般情况下不会在左边第一个（除非前两个相距>R）。

一开始二层循环外层写的i=1，这样对于数据诸如1 1 1=>0，而其实结果是1.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<set>
 8 #define INF 0x3f3f3f3f
 9 typedef long long ll;
10 using namespace std;
11 int R, n, a[1010];
12 int main()
13 {
14     while(cin >> R >> n){
15         if(R == -1&&n == -1) break;
16         for(int i = 0; i < n; i++){
17             cin >> a[i];
18         }
19         sort(a, a+n);
20         int flag=0;
21         int st = 0, ans=0;//st表示第一个未被覆盖的点 
22         for(int i = 0; i < n;){//一开始这里写的i=0，WA了
23             while(i < n&&a[i]-a[st]<=R){
24                 i++;
25             }
26             int t = i-1;//此处放一个 
27             ans++;
28             while(i < n&&a[i]-a[t]<=R){
29                 i++;
30             }
31             st = i;
32         } 
33         cout << ans << endl; 
34     }
35     return 0;
36 }