P1631 序列合并 – Xhesica's blog

链接：P1631

在做这道题前，我们来考虑这样的一个问题

已知一个n*n的数表，保证在每一行上，有a[i][j]<a[i][j+1],我们怎样求出它的第k小的值？

对于这个问题，我们

在做这道题前，我们来考虑这样的一个问题

已知一个n*n的数表，保证在每一行上，有a[i][j]<a[i][j+1],我们怎样求出它的第k小的值？

对于这个问题，我们当然不能暴力搜索，看一下限制条件，我们可以很容易的知道第一小的值肯定在a[i][1]上，那么，我们只要考虑建立一个优先队列，然后把第一列的所有数字放进去即可。

那么第2，3，4~k小怎么办？我们先来考虑第二小。假如第一小是a[1][x],第二小可能在那？可能在第一列剩下的，也有可能是a[2][x],我们只要把a[2][x]放进队列即可。

其余同理。

看懂了这个，你就明白了这道题。　

这道题就是这个思想，但是具体实现还是会抽象一点，因为n太大了，必须要在用到[i][j]的时候再算然后加入队列。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[100010];
 7 int b[100010];
 8 int n;
 9 struct num{
10     int x;
11     int y;
12     int v;
13 };
14 
15 //因为不能直接开数组，所以我们要存一下坐标，用来计算下一个数 
16 bool operator<( num a, num b ){
17     return a.v>b.v;
18 }//重载 
19 
20 priority_queue <num> q;
21 int main(){
22     cin>>n;
23     for(int i=1;i<=n;++i)
24         cin>>a[i];
25     for(int i=1;i<=n;++i)
26         cin>>b[i];
27         sort(a+1,a+1+n);
28         sort(b+1,b+1+n);
29     for(int i=1;i<=n;++i)
30     {
31         num nu;
32         nu.v=a[1]+b[i];
33         nu.x=1;
34         nu.y=i;
35         q.push(nu);
36     }
37     int k=1;
38     while(k<=n){
39         num u;
40         u.x=q.top().x+1;
41         u.y=q.top().y;
42         u.v=(a[u.x]+b[u.y]);
43         printf("%d ",q.top().v);
44         q.pop();
45         q.push(u);
46         k++;
47     }
48     return 0;
49 }

发送评论 编辑评论

发送评论编辑评论