【OJ】贪心法 Saruman's Army POJ 3069 /acmclub 12132

简介: 题目链接:点击打开链接 /* 6 10 贪心法Saruman's Army POJ 3069 1 7 15 20 30 50 ans=3*/#include#includeusing namespace std;int x[1010];int main(){// freopen("贪心法 Saruman's Army poj3069.

题目链接:点击打开链接


/*		
6 10		 贪心法Saruman's Army POJ 3069 
1 7 15 20 30 50	
ans=3
*/
#include<iostream>
#include<algorithm>
using namespace std;
int x[1010];
int main(){
//	freopen("贪心法 Saruman's Army poj3069.txt","r",stdin);

	int n,r;
  while(cin>>r>>n,n!=-1&&-1!=r){
	for(int i=0;i<n;i++){
		cin>>x[i]; 
	}
	sort(x,x+n);
	int i=0,ans1=2100000000,ans2=0;//2100000000;
//
//	while(i<n){//左向右 
//		int start=x[i];
//		while(i<n&&x[i]<=start+r)i++;
//		int point=x[i-1];
//		while(i<n&&x[i]<=point+r)i++;
//		ans1++;
////		cout<<point<<" "; 
//	}
//
	i=n-1;     //右向左 
	while(i>=0){
		int start=x[i];
		while(i>=0&&x[i]>=start-r)i--;
		int point=x[i+1];
		while(i>=0&&x[i]>=point-r)i--;
		ans2++;
//		cout<<point<<" ";
	}
	
	cout<<min(ans1,ans2)<<endl;
  }
	return 0;
}



目录
相关文章
poj 1185 炮兵阵地 (状态压缩dp)
如果你是刚刚开始做状态压缩dp,我建议你先看看 poj 3254 Corn Fields 这是一道比这一题更简单,更容易入门的题目。 还有在代码中我用了一个很巧妙的方法求一个数二进制数中1的个数 具体请看我博客中 x& (x - 1)==0 这篇文章 链接 。
39 1
|
11月前
|
机器学习/深度学习 自然语言处理
动态规划算法Oj题(一)
动态规划算法Oj题(一)
45 0
poj 1990 MooFest 树状数组
题意就是有N头牛,每头牛都有一个坐标和声调值(x, v),两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值,现在要任意两头牛之间都相互通讯一次,求总共需要花费多少能量?
45 0
|
人机交互
POJ-2524,Ubiquitous Religions(并查集模板题)
POJ-2524,Ubiquitous Religions(并查集模板题)
|
人工智能 网络架构
|
人工智能
POJ 2370 Democracy in danger(简单贪心)
Democracy in danger Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 3388   Accepted: 2508 Description In one of the...
954 0
poj supermaket (贪心)
http://poj.org/problem?id=1456 #include #include #include using namespace std; struct nod { int a; int d; }; bool cmp(nod x,nod y) { return x.
696 0