ACWing 146 Sequence

标签：code   tor   就是   push   put   lang   范围   输出   中比   

题意简述

给定\(M\)个长度为\(N\)的序列，从每个序列中任取一个数求和，求前\(N\)小和。
数据范围见题

简单口胡

• \(M = 1\)
  把原序列排个序输出完事。
• \(M = 2\)
  我们将两个序列分别假设为\(a,b\)，并已经将其排好序。

定义：

1. 第\(k\)小和为\(F(k)\)
2. 若\(a_i + b_j\)可能是\(F(k)\)的答案，我们称二元组\((i,j)\)为\(F(k)\)的候选二元组。
3. 若\(a_i + b_j\)是\(F(k)\)的答案，我们称二元组\((i,j)\)为\(F(k)\)的答案二元组。

Solution：
首先\(F(1)\)的答案二元组显然为\((1,1)\)。
考虑\(F(2)\)的候选二元组，有\((1,2),(2,1)\)，这些都有可能。
假设\(F(2)\)的答案二元组为\((2,1)\)，那么\(F(3)\)的候选二元组即为\((1,2),(2,2),(3,1)\)。
我们会发现，如果\((x,y)\)是\(F(k)\)的答案二元组，那么\((x + 1,y)\)和\((x,y + 1)\)就是\(F(k + 1)\)的候选二元组。
原因：\(a_{x + 1}\)是在\(a\)中比\(a_{x}\)大的最小的数，也就是说排名有可能只会\(+1\)，\(b_{y + 1}\)和\(b_y\)同理，所以它们是候选二元组。

• \(M > 2\)

用优先队列维护一下，每次先处理前面两排，然后将答案合并再与下一排进行计算。

但是我们会发现有时同时更新出\((x + 1,y)\)和\((x,y + 1)\)会更新出相同的二元组。
原因：设\(F(k)\)的答案二元组为\((x_0,y_0)\)
那么\(F(k + 1)\)的候选二元组就包含\(（x_0 + 1,y_0)，(x_0,y_0 + 1)\)
若\(F(k_0)(k_0 > k)\)的答案二元组为\((x_0 + 1,y_0)\)，那么其会整出\((x_0 + 2,y_0),(x_0 + 1,y_0 + 1)\)
若\(F(k_1)(k_1 > k)\)的答案二元组为\((x_0,y_0 + 1)\)，那么其会整出\((x_0,y_0 + 2),(x_0 + 1,y_0 + 1)\)，与上面的\((x_0 + 1，y_0 + 1)\)冲突。

这里你可以用map / hash 判断，也可以用《算法竞赛进阶指南》上的方法，这里不叙述，也可以看代码。

# include 
using namespace std;
int t;
int m,n;

const int M = 1005,N = 2005;

int a[M][N];

int nowi,nowj;

int A[N]; // cun chu

struct node
{
    int x,y;
    bool flag; // flag = 0 -> y + 1    flag = 1 -> x + 1;
    node() {}
    node(int _x,int _y,bool f) : x(_x),y(_y),flag(f) {}
};

bool operator  a[nowi][y.x] + a[nowj][y.y];
}

priority_queue  q;

void solve(void)
{
    while(!q.empty()) q.pop();
    q.push(node(1,1,0));
    int tot = 0;
    while(tot 

ACWing 146 Sequence

标签：code   tor   就是   push   put   lang   范围   输出   中比   

原文地址：https://www.cnblogs.com/luyiming123blog/p/14354606.html