10011.愤怒的牛
二分答案，然后贪心进行验证，即只要达到了枚举的距离能放就放，如果最后能放下就验证成功。
int n,m,ans,s[100005];
inline bool check(int x)
{
int now=1;
for (int i=1;i<m;i++)
{
int j=now+1;
while (s[now]+x>s[j] && j<=n) j++;
if (j>n) return 0;
now=j;
}
return 1;
}
int main()
{
n=read(); m=read();
for (int i=1;i<=n;i++) s[i]=read();
sort(s+1,s+n+1);
int l=0,r=s[n]-s[1];
while (l<=r)
{
int mid=(l+r)>>1;
if (check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d",ans);
return 0;
}10012.Best Cow Fences
对浮点数二分答案，然后进行验证。
验证的思想是数列中每一个数减去当前枚举的数，然后只要找到一段长度 $\geq L$ 的子序列且和 $\le 0$ 就验证成功。
我们对减去枚举答案后的子序列取前缀和，然后枚举子序列的右端点，同时维护序列左端点或以前的最小值，最后把右端点与之差分就可以得到当前最大值。每次枚举得到的最大值只要有一个 $\geq 0$ 那么就验证成功。
还有个问题是我也不知道为什么最后答案取 $l$ 就总是要小 $1$ ，加大精度到 $1e-15$ 才能过样例，然后当然会有很多TLE，甚至还有一个WA，真是玄学。
#define eps 1e-4
int n,m,s[100005];
double sum[100005];
inline bool check(double x)
{
for (int i=1;i<=n;i++) sum[i]=sum[i-1]+1.0*s[i]-x;
double mn=1e9,now=-1e9;
for (int i=m;i<=n;i++)
{
mn=min(mn,sum[i-m]);
now=max(now,sum[i]-mn);
}
return (now>=0);
}
int main()
{
n=read(); m=read();
double l=1e9,r=0;
for (int i=1;i<=n;i++) s[i]=read(),l=min(l,1.0*s[i]),r=max(r,1.0*s[i]);
while (r-l>eps)
{
double mid=(l+r)/2;
if (check(mid)) l=mid;
else r=mid;
}
printf("%d",int(r*1000));
return 0;
}10013.曲线
三分 $x$ ，每次验证所有 $f_i(x)$ 的最大值。
还有我第一次直接输出 $x$ 都过了样例然后一交全WA，这样例简直害人不浅啊！
#define eps 1e-10
int t,n,m;
struct func{
int a,b,c;
} s[100005];
inline double check(double x)
{
double ans=-1e9;
for (int i=1;i<=n;i++) ans=max(ans,(1.0*s[i].a*x*x+1.0*s[i].b*x+1.0*s[i].c));
return ans;
}
int main()
{
t=read();
while (t--)
{
n=read();
for (int i=1;i<=n;i++) s[i].a=read(),s[i].b=read(),s[i].c=read();
double l=0,r=1000;
while (r-l>eps)
{
double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
if (check(r_mid)>check(l_mid)) r=r_mid;
else l=l_mid;
}
printf("%.4f\n",check(l));
}
return 0;
}10014.数列分段 II
还是二分答案，然后贪心验证。
这题我去年就写过了，这次就懒得写了，直接从洛谷复制过来，所以我也不知道我当时为什么要写递归版的二分。
int n,m,s[100005];
void search(int l,int r)
{
if (l>r)
{
printf("%d",l);
return;
}
int mid=(l+r)/2;
int sec=0,sum=0;
for (int i=1;i<=n;i++)
{
if (sum+s[i]>mid)
{
sum=0;
sec++;
}
sum+=s[i];
}
if (sec>=m) l=mid+1;
else r=mid-1;
search(l,r);
}
int main()
{
n=read(); m=read();
int l=0,r=0;
for (int i=1;i<=n;i++)
{
s[i]=read();
l=max(l,s[i]);
r+=s[i];
}
search(l,r);
return 0;
}10015.扩散
直接把所有点连起来跑Kruskal就行了，懒得写二分。
#define pr pair<int,int>
#define mp make_pair
struct point{
int x,y;
} pt[55];
struct Edge{
int st,ed,w;
} edge[2505];
int n,m,a,b,c,fa[55],cnt,ans;
inline void add(int u,int v,int w)
{
edge[++cnt].st=u;
edge[cnt].ed=v;
edge[cnt].w=w;
}
inline void init()
{
for (int i=1;i<=n;i++)
fa[i]=i;
}
int getfa(int x)
{
if (x==fa[x]) return fa[x];
fa[x]=getfa(fa[x]);
return fa[x];
}
inline bool merge(int x,int y)
{
int gfx=getfa(x),gfy=getfa(y);
if (gfx==gfy) return 0;
fa[gfx]=gfy;
return 1;
}
inline bool cmp(Edge x,Edge y)
{
return x.w<y.w;
}
inline void kruskal()
{
for (int i=1;i<=cnt && n;i++)
{
int x=edge[i].st,y=edge[i].ed;
if (merge(x,y))
{
n--;
ans=max(ans,edge[i].w);
}
}
}
int main()
{
n=read();
init();
for (int i=1;i<=n;i++) pt[i].x=read(),pt[i].y=read();
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
add(i,j,(abs(pt[i].x-pt[j].x)+abs(pt[i].y-pt[j].y)+1)>>1);
sort(edge+1,edge+cnt+1,cmp);
kruskal();
printf("%d",ans);
return 0;
}10016.灯泡
设影子在墙上的部分的高度为 $x$ ，用相似可以推出影子总长度
$$L=D\times \dfrac {h-x}{H-x} +x$$
对其进行变形
$$L= \dfrac {D\times (H-h)}{x-H} + ( x - H ) + H + D$$
这是一个对勾函数左侧，是个凸函数，所以三分即可。
#define eps 1e-5
int t;
double H,h,D;
inline double check(double x)
{
return D*(h-x)/(H-x)+x;
}
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%lf%lf%lf",&H,&h,&D);
double l=0,r=h;
while (r-l>eps)
{
double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
if (check(r_mid)<check(l_mid)) r=r_mid;
else l=l_mid;
}
printf("%.3f\n",check(l));
}
return 0;
}10017.传送带
我们假设在 $AB$ 段走到 $M$ 点，然后走到 $CD$ 段的 $N$ 点，那么可以得到时间为
$$T= \dfrac {AM}{P} + \dfrac {MN}{R} + \dfrac {ND}{Q}$$
很显然我们的目标就是找到合适的 $M$ 和 $N$ 让时间最小。
对于 $M$ ，如果我们知道 $k= \dfrac {AM}{AB}$ ，那么就可以确定 $M$ 的坐标为
$$M(Ax+(Bx-Ax)\times k,Ay+(By-Ay)\times k)$$
函数是个凹函数，证明，所以我们可以对 $k\in (0,1)$ 进行三分。
对于 $CD$ 段的 $N$ 也同理，进行两次三分后也就能确定答案了。
#define eps 1e-5
double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,p,q,r;
inline double get_dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double check2(double k1,double k2)
{
double Mx=Ax+(Bx-Ax)*k1,My=Ay+(By-Ay)*k1,Nx=Cx+(Dx-Cx)*k2,Ny=Cy+(Dy-Cy)*k2;
return get_dis(Ax,Ay,Mx,My)/p+get_dis(Mx,My,Nx,Ny)/r+get_dis(Nx,Ny,Dx,Dy)/q;
}
inline double check(double k)
{
double l=0,r=1;
while (r-l>eps)
{
double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
if (check2(k,r_mid)>check2(k,l_mid)) r=r_mid;
else l=l_mid;
}
return check2(k,l);
}
int main()
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&Ax,&Ay,&Bx,&By,&Cx,&Cy,&Dx,&Dy,&p,&q,&r);
double l=0,r=1;
while (r-l>eps)
{
double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
if (check(r_mid)>check(l_mid)) r=r_mid;
else l=l_mid;
}
printf("%.2f",check(l));
return 0;
}