poj3069 Saruman's Army（貪心）

https://vjudge.net/problem/POJ-3069

弄清楚一點，第一個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 }

轉載于:https://www.cnblogs.com/Surprisezang/p/9000523.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/250335.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/250335.shtml
英文地址，請注明出處：http://en.pswp.cn/news/250335.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！