首页 > 代码库 > CSU-1408: 种植树苗
CSU-1408: 种植树苗
Description
如下图所示,我们在门前一条笔直的道路上栽了N棵树苗。
但是,最近我们发现,如果两棵树苗的距离小于一个常数D,这两棵树苗的发育都会受到阻碍。因此我们决定移除一些树苗,从而使任意两棵树苗的距离都不小于D,并且我们希望留下的树苗越多越好。
Input
输入的第一行包含一个整数T (T > 0),表示一共有T组测试数据。
对于每组测试数据,第一行包含两个整数N,D (1 ≤N ≤ 105, 1≤ D ≤ 109)。第二行包含N个整数a1,a2, ...,aN (0 <a1 <a2 < ... <aN < 109),其中ai (1 ≤ i ≤N)表示第i棵树苗的位置。
Output
对于每组测试数据,输出我们最多可以留下多少棵树苗,并且任意两棵树苗的距离都不小于D。
Sample Input
5
1 3
7
2 1
3 4
2 2
3 4
7 2
1 2 3 5 6 8 9
7 4
1 2 3 5 6 8 9
Sample Output
1
2
1
4
3
HINT
Source
中南大学第八届大学生程序设计竞赛
贪心题: 以第一个坐标为起始点,如果后续序列的数与之距离小于D,表示需要移除标记为1,否则起始点更新为当前数,最后统计标记为0的数即可。
#include<cstring> #define N 100005 int a[N],dp[N]; int main() { int t,n,d,i,j,ans; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&d); for(i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); ans=a[1]; for(i=2;i<=n;i++) { if(a[i]-ans<d) dp[i]=1; else ans=a[i]; } ans=0; for(i=1;i<=n;i++) if(!dp[i]) { //printf("%d",a[i]); ans++; } printf("%d\n",ans); //printf("\n"); }
CSU-1408: 种植树苗
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。