[线段树]/[水法] Jzoj P100036 随机

阅读量：5028 次

发布时间：2019-06-12

本文共 2740 字，大约阅读时间需要 9 分钟。

Description

Input

Output

Sample Input

5 9 20 15 6 10

Sample Output

Data Constraint

Hint

水法题解

正解是不可能正解的，这辈子都不可能打正解了

Ans=min(max(|ai−aj|,j−i+1))

对于所有区间，发现我们只取左右端点是最优的

因为，如果不包括左右端点的话，剩下的部分都是没用的

所以可以直接把左右端点放到取的两个数那，这样的话它的m值可以变小，所以就不是最优的

基于这个思想，可以在循环时，将当前求出的最小的ans当成要找区间的大小的最大值

也就是如果要取更小的答案，就必须要小于当前ans，所以剩下区间的m的不能大于ans，可以更快找到更小的答案

然后，每次对于一个m，跑n-m+1次，一定是区间的左右端点，具体看上

时间复杂度由时间来定，很玄学，刚好卡过（不过很短啊(～￣▽￣)～）

正解题解

假设我们现在的区间长度是m，最小值是min，将右端点右移，m++，min将可能会减小

我们确定一个左端点l，假设右端点是r，那么一定当r位于m>=min的临界点上max(m, min)菜会最小

证明：假设现在在临界点上,r–,则m–，min可能增加，答案不可能减少

r++，m++，min可能减少，答案不可能减少。

所以我们从[1..2]开始，如果m >= min，则r++，否则l++。

用线段树维护min

水法代码

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int n,ans,a[1000010]; 5 int main() 6 { 7     freopen("random.in","r",stdin); 8     freopen("random.out","w",stdout); 9     scanf("%d",&n);10     for (int i=1;i<=n;i++) scanf("%d",&a[i]);11     ans=n;12     for (int i=2;i
       
        abs(a[j]-a[j+i-1])) ans=abs(a[j]-a[j+i-1]);15     printf("%d",(ans<2?2:ans));16     return 0;17 }

正解代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int inf=2000000000; 7 int n,ans,a[1000010],p[1000010],w[1000010],tot; 8 struct edge { int x,y; }k[1000010]; 9 struct node { int l,r,v,size; }tree[10000010];10 bool cmp(edge x,edge y) { return x.x
         
          2) tree[d].v=0; else tree[d].v=inf;18     }19     else 20     {21         int mid=(l+r)/2;22         if (x<=mid) insert(d*2,l,mid,x,y); else insert(d*2+1,mid+1,r,x,y);23         tree[d].v=min(tree[d*2].v,tree[d*2+1].v);24         if (tree[d*2].r&&tree[d*2+1].l) tree[d].v=min(tree[d].v,p[tree[d*2+1].l]-p[tree[d*2].r]);25         if (tree[d*2].l) tree[d].l=tree[d*2].l; else tree[d].l=tree[d*2+1].l;26         if (tree[d*2+1].r) tree[d].r=tree[d*2+1].r; else tree[d].r=tree[d*2].r;27     }28 }29 int main()30 {31     freopen("random.in","r",stdin);32     freopen("random.out","w",stdout);33     scanf("%d",&n);34     for (int i=1;i<=n;i++) scanf("%d",&a[i]),k[i].x=a[i],k[i].y=i;35     sort(k+1,k+n+1,cmp);36     tot=0;37     for (int i=1;i<=n;i++) tot+=(k[i].x!=k[i-1].x),w[k[i].y]=tot,p[tot]=k[i].x;38     for (int i=1;i<=tot*10;i++) tree[i].v=inf;39     insert(1,1,tot,w[1],1),insert(1,1,tot,w[2],1);40     ans=inf;41     int l=1,r=2;42     while (r<=n)43     {44         ans=min(ans,max(tree[1].v,r-l+1));45         if (l==r-1||tree[1].v>r-l+1)46         {47             if (r==n) break;48             r++;49             insert(1,1,tot,w[r],1);50         }51         else insert(1,1,tot,w[l],-1),l++;52     }53     printf("%d",ans);54     return 0;55 }