JZOJ6019. 【GDOI2019模拟2019.2.14】小b爱实数

Description

Data Constraint

Solution

（转自出题人题解，因为实在是太详细了不知道说什么）

注意精度，被卡了好多次。。。。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 1000005
#define db double 
#define E 0.000001
using namespace std;

int n,i,j,k,a[maxn],cnt,ansi;
db f,ans;
struct point{
	db x,y;
} p[maxn];
int cmp(point a,point b){return E<b.y-a.y;}
char ch;

int main(){
	freopen("real.in","r",stdin);
	freopen("real.out","w",stdout);
	scanf("%lf",&f);
	ch=getchar(); while (ch!='0'&&ch!='1') ch=getchar();
	while (ch=='0'||ch=='1') a[++n]=ch-'0',ch=getchar();
	cnt=0;
	for(i=1;i<=n;i++) cnt+=a[i],p[i].x=i,p[i].y=f*i-cnt;
	sort(p+1,p+1+n,cmp);
	ans=(db)cnt/n,ansi=0;
	for(i=1,j=i+1;i<n;i++,j++) {
		db tmp=abs((p[i].y-p[j].y)/(p[i].x-p[j].x));
		int w=min(p[i].x,p[j].x);
		if (E<ans-tmp||abs(tmp-ans)<E&&w<ansi) 
			ans=tmp,ansi=w;
	}
	printf("%d
",ansi);
}