poj3069 Saruman's Army(贪心)

时间:2022-07-07 17:09:35

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

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

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

 #include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int R, n, a[];
int main()
{
while(cin >> R >> n){
if(R == -&&n == -) break;
for(int i = ; i < n; i++){
cin >> a[i];
}
sort(a, a+n);
int flag=;
int st = , ans=;//st表示第一个未被覆盖的点
for(int i = ; i < n;){//一开始这里写的i=0,WA了
while(i < n&&a[i]-a[st]<=R){
i++;
}
int t = i-;//此处放一个
ans++;
while(i < n&&a[i]-a[t]<=R){
i++;
}
st = i;
}
cout << ans << endl;
}
return ;
}