[USACO16JAN]Angry Cows G 解题报告

一图流

参考代码:

#include
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout)
#define gc getchar
#define pc putchar
namespace IO{
	template
	inline void read(T &s){
		s=0;char ch=gc();bool f=0;
		while(ch<'0'||'9'
	inline void read(T &s,A &...a){
		read(s);read(a...);
	}
	inline bool blank(char c){
		return c==' ' or c=='\t' or c=='\n' or c=='\r' or c==EOF;
	}
	inline void gs(std::string &s){
		s+='#';char c=gc();
		while(blank(c) ) c=gc();
		while(!blank(c) ){
			s+=c;c=gc();
		}
	}
	inline void gs(char *s){
		char ch=gc();
		while(blank(ch) ) {ch=gc();}
		while(!blank(ch) ){
			*s++=ch;ch=gc();
		}
		*s=0;
	}
};
using IO::read;
using IO::gs;
const int inf=1e9;
const int N=5e4+3;
int n;
int a[N];
int f[N],g[N];
int main(){
	filein(a);fileot(a);
	int n;read(n);
	for(int i=1;i<=n;++i){
		read(a[i]);
	}
	std::sort(a+1,a+1+n);
	n=std::unique(a+1,a+1+n)-a-1;
	for(int i=1;i<=n;++i){
		f[i]=g[i]=inf;
	}
	int j=1;
	f[1]=0;
	for(int i=2;i<=n;++i){
		while(j+1f[j+1]+1)
			++j;
		f[i]=std::min(a[i]-a[j],f[j+1]+1);
	}
	j=n;
	g[n]=0;
	for(int i=n-1;i>=1;--i){
		while(j-1>i and a[j-1]-a[i]>g[j-1]+1)
			--j;
		g[i]=std::min(a[j]-a[i],g[j-1]+1);
	}
	db ans=inf;
	int l=1,r=n;
	while(l