从恒定状态出发,求解未知状态

 

   许多问题都是拥有一个恒定的状态,从这个状态进行演化、转移,产生性质相同,规模更小的子问题。于是我们以此入手,分析出那个恒定的状态与权值,再看如何进行转移产生另一个子问题的解.

例如下面这个题:

中位数问题

给出一个长度为N的非负整数序列A_i,对于所有1 < = k < = (N + 1) / 2, 输出前1,3,5,…个数的中位数。

Input

第1行为一个正整数N,表示了序列长度。 N<=10^5

第2行包含N个整数A_i (-10^9 < = A_i < = 10^9)

 

Output

如题所示。

 

输入数据 1

7

5 7 8 2 3 1 9

输出数据 1

5

7

5

5

 

题解:

就本题的本质来说,就是求一些数字的中位数。如果只是求一次中位数的话,很简单,快速一下即可,时间复杂度为O(N*Log2N),当然如果你对快排理解得够深刻,可以写到O(N).

但本题是多次求中位数,而且是前1,3,5,7,9……个数字的中位数,这明显是一个公差为2的等差数列。经过分析可得到

1:对于一个升序的数列,如果每次给它插入或减少2个数字,中位数所位的位置只会发生一个位置的偏移,或者不变。以减少为例来说,如果减少的2个数字,一个在中位数位置的左边,一个在右边,则中位数位置不变;如果2个均在中位数位置的左边,则中位数右移一位,反之则左移一位。

2:由于本题是事先就给出所有的数字,属于离线询问,所以对于原数列,经过一次快排,我们可根据中位数的定义知道其位置,进而知道其权值。

3:根据上一条所推出来的恒定的量,我们分析下接下来要解决的问题:求前5个数字的中位数。很明显,我们只需要从排序的数列中去掉最后2个数字即可,产生的后果如第1条所分析。当然此时我们应能做到快速找到去掉的这2个数字在升序数列中的位置,根据其位置与中位数位置的关系进行相应的处理。

4:得到相应结果,我们必须从升序数列中去掉刚才那2个数字,不难发现此题需要不断的删除元素,于是采用链表结构进行处理。

5:不断执行上叙步骤,得到所有的解,然后进行输出即可

代码如下:

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int b[20000],ans[20000],v[20000];

struct node {

       int last,next,c,p;

} a[200000];

bool cmp(node x,node y) {

       if (x.c==y.c)

              return x.p<y.p;

       else

              return x.c<y.c;

}

int main() {

       int t;

       int n,p,ss=0,sl=0,sr=0,s,sx;

       scanf("%d",&n);

       for (int i=1; i<=n; i++) {

              scanf("%d",&b[i]);

              a[i].c=b[i];

              a[i].p=i;

       }

       sort(a+1,a+1+n,cmp);

       for (int i=1; i<=n; i++) {

              a[i].last=i-1; //第i个元素左边是i-1

              a[i].next=i+1;  //右边是i+1

              v[a[i].p]=i;

       }

       s=a[n/2+1].c; //权值

       sx=n/2+1; //位置

       if (n%2==0)

              ans[++ss]=(a[n/2].c+a[n/2+1].c)/2;

       else

              ans[++ss]=a[n/2+1].c;

 

       for (int i=n; i>1; i-=2)

              //v[i]代表读入的第i个数字,它在链表中的位置是多少

       {

              if (v[i]<sx&&v[i-1]>sx||v[i]>sx&&v[i-1]<sx)

                     //加入的两个位置,一个大于sx,一个小于则中位数不变

              {

                     ans[++ss]=a[sx].c;

              } else if (v[i]<=sx&&v[i-1]<=sx)

                     //加入的两个位置,均小于等于sx,则中位数右移一下

              {

                     sx=a[sx].next;

                     ans[++ss]=a[sx].c;

              } else {

                     sx=a[sx].last;

                     ans[++ss]=a[sx].c;

              }

              int x=a[v[i]].last,y=a[v[i]].next;

              //x......i.....y ,删去i这个元素

              a[y].last=x;

              a[x].next=y;

              x=a[v[i-1]].last;

              y=a[v[i-1]].next;

              //删去i-1这个元素

              a[y].last=x;

              a[x].next=y;

       }

       for (int i=ss; i>0; i--)

              printf("%d\n",ans[i]);

       return 0;

}

 

例题2:Ksum

给你一个长度为n的一个正整数数组,于是这个数列有n(n+1)/2个子段 现在求出了这n(n+1)/2个子段之和,并降序排序,请问前K个数是多少。

 

Input

第一行包含两个整数 n 和 k。 接下来一行包含 n 个正整数,代表数组。 ai≤10^9 k≤n(n+1)/2, n≤100000,k≤100000

 

Output

输出 k 个数,代表降序之后的前 k 个数,用空格隔开

 

输入数据 1

3 4

1 3 4

输出数据 1

8 7 4 4

 

通过分析不难得出

1:整个数列的最大值明显为所有数字之和,即数字区间【1..N】

2:现在希望得到权值第2大的区间和,明显应该将区间【1..N】的左端点1右移1位,或右端点N左移1位,产生于两个子区间【1..N-1】和【2..N】。但它们两个的权值,哪一个更大一些呢?没事,丢到堆中即可。

3:接着对衍生出来的两个子区间【1..N-1】和【2..N】继续衍生,会发现区间【2..N-1】会被衍生出来2次。我们可以强行去掉其中的一个,保留另一个。于是规定对于某个区间

【L,R】只有当R=N时,才允许其左边界向右移动。最终可得到以下衍生图:

 

代码如下:

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

struct node {

       int l,r;

       long long s;

} t,z;

int n,k,a[100010];

long long s;

priority_queue<node> q;

bool operator <(node a,node b) {

       return a.s<b.s;

}

int main() {

       scanf("%d%d",&n,&k);

       for(int i=1; i<=n; i++)

       {

              scanf("%d",&a[i]);

              s+=a[i];

       }

       t.s=s;

       t.l=1;

       t.r=n;

       q.push(t);

       for(int i=1; i<=k; i++)

       {

              t=q.top();

              q.pop();

              printf("%lld ",t.s);

              z.l=t.l;

              z.r=t.r-1;

              z.s=t.s-a[t.r];

              q.push(z);

              if(t.r==n) {

                     z.l=t.l+1;

                     z.r=t.r;

                     z.s=t.s-a[t.l];

                     q.push(z);

              }

       }

       return 0;

}

 

邻值查找 

给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 Ai,求:

min|Ai−Aj|,其中1≤j<i

以及令上式取到最小值的 j(记为 Pi)。若最小值点不唯一,则选择使 Aj 较小的那个。

输入格式

第一行输入整数n,代表序列长度。

第二行输入n个整数A1…An,代表序列的具体数值,数值之间用空格隔开。

输出格式

输出共n-1行,每行输出两个整数,数值之间用空格隔开。

分别表示当i取2~n时,对应的min|Ai−Aj|和Pi的值。

数据范围

n≤10^5,|Ai|≤10^9

输入样例:

3

1 5 3

输出样例:

4 1 //对于5来说,在它左边并与其差的绝对值最小的是1,差值为4

2 1 //对于3来说,在它左边并与其差的绝对值最小的是5,差值为2

题解:

观察可得,既要快速找到某元素左右两边的元素,又要高效的删除任一个元素,采用链表进行存储再合适不过了。于是按照上面的思路,维持一个从小到大排序的链表,先找到原始下标最大的结点,向其左右结点求取离它最近的元素,之后删去该结点,重新接上链表,重复该过程即可。一开始排序消耗的时间复杂度是O(nlogn),链表的单次操作时间复杂度是O(1),总的时间复杂度为O(nlogn)。当然,也可以使用STL现成的容器set来解决本题,可以在对数的时间内找到离某元素最近的元素,总的时间复杂度也为O(nlogn)。

代码如下:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,int> PII;

const int maxn = 100010;

int n,l[maxn],r[maxn],p[maxn];

PII a[maxn],ans[maxn];

 

int main() {

       cin>>n;

       for(int i = 1; i <= n; i++) {

              cin>>a[i].first;

              a[i].second = i;

       }

       sort(a + 1, a + n + 1);

       a[0].first = -3e9,a[n + 1].first = 3e9;

       //哨兵结点,头尾结点

       for(int i = 1; i <= n; i++) {

              l[i] = i - 1,r[i] = i + 1;

              p[a[i].second] = i;

       }

       for(int i = n; i > 1; i--)

       {

              int j = p[i],left = l[j],right = r[j];

              ll left_value = abs(a[left].first - a[j].first);

              ll right_value = abs(a[right].first - a[j].first);

              if(left_value <= right_value)

                     ans[i] = {left_value,a[left].second};

              else

                     ans[i] = {right_value,a[right].second};

              l[right] = left,r[left] = right;

       }

       for(int i = 2; i <= n; i++)

              cout<<ans[i].first<<" "<<ans[i].second<<endl;

       return 0;

}

 

上述诸题均还有其它方法进行求解,在此不再赘述,但本文所担的思维方式,在计算机许多算法中都有体现,例如dijkstra求最短路,背包算法等等。

算法的其实就是在不断的从一个开始状态出发,进行状态的转移,只是这个转移过程,我们可以通过许多方法与手段让它更快一些罢了。。

上一篇:802.11a OFDM symbol


下一篇:LTE物理层