题解 P3132 【[USACO16JAN]愤怒的奶牛Angry Cows】

qzr_ · 2018-10-26 21:47:13 · 题解

实际上楼下的题解还是可以继续优化的， 因为f与x的差都具有单调性，而答案去其中的最大值，所以对于j>i,f[j]的最优决策点一定在f[i]的决策点的右边，所以就可以利用这个性质优化了。 时间复杂度O（n）（除开排序） 下面贴代码（f1对应楼下g）

#include<cstdio>
#include<algorithm>
using namespace std;
 long n,x[50001],f[50001],f1[50001],ans=0x3f3f3f3f,l,r,now;
 bool ans1;
int main()
{
freopen("a.in","r",stdin);
 scanf("%ld",&n);
 for(int i=1;i<=n;i++)
  scanf("%ld",&x[i]);
 sort(x+1,x+n+1);
 f[1]=0;
 now=1;
 for(int i=2;i<=n;i++)
  {
   while(x[i]-x[now]>=f[now]+1&&now<i-1) now++;
   if(f[now]+1>x[i]-x[now-1])
    now--;
   f[i]=max(f[now]+1,x[i]-x[now]);
  }
 f1[n]=0;now=n;  
 for(int i=n-1;i>=1;i--)
 {
  while(x[now]-x[i]>=f1[now]+1&&now>i+1) now--;
  if(f1[now]+1>x[now+1]-x[i]&&now<n) now++;
  f1[i]=max(f1[now]+1,x[now]-x[i]);
 }
 now=1;
 for(int i=1;i<=n;i++)
 {
 l=r;
  while(x[i]-x[now]>=(f[now]+1)*2&&now<i-1) 
   now++;
  if(x[i]-x[now-1]<(f[now]+1)*2) now--;
  if(max(f1[i]+1,max(f[now]+1,(x[i]-x[now])/2))<ans||(max(f1[i]+1,max(f[now]+1,(x[i]-x[now])/2))==ans&&((x[i]-x[now])%2<ans1)))
   {
   ans=max(f1[i]+1,max(f[now]+1,(x[i]-x[now])/2));
   if((x[i]-x[now])/2>=f[now]+1&&(x[i]-x[now])/2>=f1[i]+1)
   ans1=(x[i]-x[now])%2;
  else ans1=0;
 }
 }
  printf("%ld",ans);
  if(ans1)
   printf(".5");
   else printf(".0");
 return 0;
}

因为我写得丑，才跑了142ms（rank1写的似乎是nlogn的）