P2678 [NOIP2015 提高组] 跳石头

思路：

运用两次数组比较，按照序号和前后相差距离的大小比较排序。

代码：首次尝试30分

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
 
int m,n;
long long l;
int a[50010];
struct node{
	int id;
	int cha;
}; 
node b[50010];
node c[50010];

bool cmp(node aa,node bb){
	int id1 = aa.id;
	int id2 = bb.id;
	
	if(aa.cha == bb.cha){
		int x1 = b[id1].cha + b[id1+1].cha;
		int x2 = b[id2].cha + b[id2+1].cha;
		if(x1<x2) return aa.cha + b[id1+1].cha > bb.cha + b[id2+1].cha;
		else return aa.cha + b[id1+1].cha < bb.cha + b[id2+1].cha;
	}
	return aa.cha < bb.cha;
}
bool cmp1(node aa,node bb){
	return aa.id<bb.id;
}
int main()
{
	scanf("%lld%d%d",&l,&n,&m);//分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i].cha = a[i] - a[i-1];
		b[i].id = i;
	}
	//最多移走m个石头，在输入的时候将相邻最小的两块石头移走，看移走m块和m-1块是不是效果相同 
	//差数组里存下标和“与前一块石头的距离差”	 
	sort(b+1,b+n+1,cmp);
	//先把前m个单独存储出来
	for(int i=1;i<=m;i++){
		c[i].id = b[i].id;
		c[i].cha = b[i].cha;
	} 
	sort(b+1,b+n+1,cmp1);
	
	for(int i=1;i<=m;i++){
		//看看移走哪几块
//		cout<<c[i].cha<<" "<<c[i].id<<endl;
		//更新
		int id = c[i].id;
		int cha = c[i].cha;
		
		b[id+1].cha += cha;		 
	}
	
//	for(int i=1;i<=n;i++){
//		printf("%d %d\n",b[i].id, b[i].cha);
//	}
	sort(b+1,b+n+1,cmp);
	
	cout<<b[m+1].cha;
	return 0;
 } 

结果：

 AC代码：借鉴洛谷题解zhaowangji的代码加上自己的理解修改代码如下

//采用二分，二分的是最终的答案距离。
//设最大能跳跃的距离为mid,看在该条件下需要移走的石头 
//如果需要移走的石头数大于m，说明说明该mid太大，答案在左半段

//采用二分，二分的是最终的答案距离。
//设最大能跳跃的距离为mid,看在该条件下需要移走的石头 
//如果需要移走的石头数大于m，说明该mid太小，答案在右半段
 #include<iostream>
 using namespace std;
 int l,m,n;
 int dis[50007];//每个石头到起点的距离
 int main()
 {
 	cin>>l>>n>>m;
 	//第i个石头距离开头的长度 
 	for(int i=1;i<=n;i++)
		cin>>dis[i];
	dis[n+1]=l;//终点
	//二分时左闭右开 
	int left=0,right=l+1,mid;//两个极值，但注意left可以取到，而right不能取到
	while(left+1<right)
	{
		mid=(left+right)/2;
		int sum=0,x=dis[0];//sum是当前答案下要移多少石头，x是当前起跳的石头（初始为起点）
		for(int i=1;i<=n+1;i++)//注意是n+1（因为有终点啊）
		{
			if(dis[i] - x < mid)
			    sum++;//起跳距离小于当前答案，说明要移走
		else 
			x=dis[i];//换到当前位置起跳
        }
		if(sum<=m)	
			left=mid;//要移的数量小于等于题目要求，说明答案还可以更大
		else 
			right=mid;//该情况数值过大，答案在左半段 
	}
	cout<<left<<endl;//left即为答案
	return 0;
 } 

结果：