mspaint 9448 11360 11690

题目传送门

#include<bits/stdc++.h>
using namespace std;
int n,m,c,a[1000001],b[1000001];
bool check(int x)
{
	int sum=0;
	bool bb=true;//判断是否有子弹 
	for(int i=1;i<=n;i++)//初始化 
	{
		b[i]=a[i];
	}
	for(int i=1;i<=n;i++)
	{
		b[i]-=sum;//敌人减去之前所用的时间，因为一秒等于一米 
		if(bb==false)//如果没子弹
		{
			//bb=true   我也不知道为什么不能加，加的话80分 
			sum+=x;//sum加上换弹时间
			b[i]-=x;//敌人减去换弹时间，因为一秒等于一米
		}
		if(b[i]<0)return false;//如果敌人到达山头，Lucky则牺牲 
		if(b[i]>m)//如没到射程范围内 
		{
			sum+=b[i]-m;//sum加上敌人到射程内的时间
			b[i]=b[i]-m;//敌人减去到射程内的行走的距离，因为一秒等于一米
		}
		if(bb==true&&b[i]<=m)//如既有子弹又在射程内，消耗子弹 
		{
			bb=false;
		}
	}
	return true;
}
int main()
{
	cin>>n>>m;
	int mid,r=1,l=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		l=max(l,a[i]);
	}
	sort(a+1,a+1+n);//从小到大排序 
	while(l-r>1)//二分答案 
	{
		mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}
	cout<<r;
	return 0;
}

实数二分

double r=0,l=10000000;
	while(l-r>1e-4)//负4，看情况，题目要求保留几位小数+1
	{
		double mid=(r+l)/2;
		if(check(mid)==true)l=mid;
		else r=mid;
	}

消息传递P1218

using namespace std;
int n;
double k,a[1000001];
bool check(double x)
{
	double last=a[1]+x;
	for(int i=2;i<=n;i++)
	{
		if((last+k)<a[i]-x)return false;
		else last=min(last+k,a[i]+x);
	}
	return true;
}
int main()
{
	cin>>k>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	double r=0,l=a[n]-a[1];
	while(l-r>1e-4)
	{
		double mid=(r+l)/2;
		if(check(mid)==true)l=mid;
		else r=mid;
	}
	printf("%.3f",l);
	return 0;
}

双指针模板

int i=1,j=1;
	while(i<=n&&j<=n)//到达边界则结束循环 
	{
		if(...)//当满足某项条件时 
		{
			j++;//指针指向另外一个下标 
		}else{//否则 
			i++;//另外一个针指向另外一个下标
		}
	}

3559

#include <iostream>
using namespace std;
int n,m,a[1000001];
int b[1000001],sum,ans1=1000000000,ans2=1;
int main(){ 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int i=1,j=1;
	b[a[1]]++;
	sum=1;
	while(i<=n&&j<=n) 
	{
		if(sum==m)
		{
			if((i-j+1)<(ans1-ans2+1))
			{
				ans1=i;
				ans2=j;
			}
			b[a[j]]--;
			if(b[a[j]]==0)sum--;
			j++; 
		}else{ 
			i++;
			b[a[i]]++;
			if(b[a[i]]==1)sum++;
		}
	}
	cout<<ans2<<" "<<ans1;
	return 0;
}