j**l
发帖数: 2911 | 1 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
pair。这道题有O(n)的算法么？
这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
的每行每列都是严格升序排列的，所以C是一个Young Tableau
虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
小于这个新问题? 也就是原问题和新问题，不是等价的。 | r****o
发帖数: 1950 | 2 问一下，Young Tableau是怎么定义的？是不是每行每列都顺序递增就是Young Tableau?
C
小n
【在 j**l 的大作中提到】
: 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
: 一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
: pair。这道题有O(n)的算法么？
: 这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
: 的每行每列都是严格升序排列的，所以C是一个Young Tableau
: 虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
: 个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
: 小于这个新问题? 也就是原问题和新问题，不是等价的。
| k***e
发帖数: 556 | 3 这也太难了
不搞combinatorial的人连啥是young tableau都不知道
C
小n
【在 j**l 的大作中提到】
: 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
: 一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
: pair。这道题有O(n)的算法么？
: 这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
: 的每行每列都是严格升序排列的，所以C是一个Young Tableau
: 虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
: 个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
: 小于这个新问题? 也就是原问题和新问题，不是等价的。
| m*****g
发帖数: 226 | | Z*****Z
发帖数: 723 | 5 Young Tableau的情况可以用最小堆做到nlgn吗？
btw:数组可以转化到YT，但是YT不一定能转化回去吧？
C
小n
【在 j**l 的大作中提到】
: 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
: 一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
: pair。这道题有O(n)的算法么？
: 这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
: 的每行每列都是严格升序排列的，所以C是一个Young Tableau
: 虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
: 个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
: 小于这个新问题? 也就是原问题和新问题，不是等价的。
| S*******n
发帖数: 1867 | 6 两个问题不等价
这个问题只是Young tableau的一个特殊情况
就是说一个young tableau 问题不能转化为这个问题
C
小n
【在 j**l 的大作中提到】
: 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
: 一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
: pair。这道题有O(n)的算法么？
: 这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
: 的每行每列都是严格升序排列的，所以C是一个Young Tableau
: 虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
: 个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
: 小于这个新问题? 也就是原问题和新问题，不是等价的。
| j**l
发帖数: 2911 | 7 是的，这个Young Tableau比较特殊，也就是说每行的差量是一样的，每列的差量也是
一样的
【在 S*******n 的大作中提到】
: 两个问题不等价
: 这个问题只是Young tableau的一个特殊情况
: 就是说一个young tableau 问题不能转化为这个问题
:
: C
: 小n
| j**l
发帖数: 2911 | 8 那么，在行差量相同和列差量相同的Young Tableau中，应该可以O(n)找出前n个最小？ | S*******n
发帖数: 1867 | 9 你这个题和mergeSort里面那个merge函数有点相似
如果题目的意思是A(B)里面的数不能和A(B)自身的数配对的话 这个题应该很好解阿
总的运算应该还是n..因为只找n个..
vector(int) vecForResult=vector(n,0);
vecForResult[0]=A[0]+B[0];
int i=1;
int indexA=0,indexB=0;
while(i
{
bool isMoveB= A[indexA]+B[indexB+1]<= A[indexA+1]+B[indexB];
if(isMoveB==1)
{
vecForResult[i]=A[indexA]+B[indexB+1];
indexB++;
}
else
{
vecForResult[i]=A[indexA+1]+B[indexB];
indexA++;
}
i++;
}
correct me if I am wrong
C
小n
【在 j**l 的大作中提到】
: 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
: 一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
: pair。这道题有O(n)的算法么？
: 这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
: 的每行每列都是严格升序排列的，所以C是一个Young Tableau
: 虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
: 个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
: 小于这个新问题? 也就是原问题和新问题，不是等价的。
| S*******n
发帖数: 1867 | 10 刚刚写了一个解法 在下面
我觉得把这个换为Young tableau的问题换复杂了
【在 j**l 的大作中提到】
: 那么，在行差量相同和列差量相同的Young Tableau中，应该可以O(n)找出前n个最小？
| | | j**l
发帖数: 2911 | 11 画图比较直观
A = 1, 2, 3, 4
B = 5, 6, 7, 8
则C是
6 7 8 9
7 8 9 10
8 9 10 11
9 10 11 12
则任何顺序能打印这16个和的程序应该输出
6 7 7 8 8 8 9 9 9 9 10 10 10 11 11 12
前4个是6 7 7 8
【在 S*******n 的大作中提到】
: 刚刚写了一个解法 在下面
: 我觉得把这个换为Young tableau的问题换复杂了
| D***h
发帖数: 183 | 12 你好像喜欢把简单问题复杂化? 不过我喜欢你的发散思维.
直接simulate merge sort不就是O(n)了。
C
小n
【在 j**l 的大作中提到】
: 原题是这样的，数组A和数组B的长度都是n, 且都严格单调递增，取A中一个元素和B中
: 一个元素组成一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个
: pair。这道题有O(n)的算法么？
: 这道题实际上是可以转换成Young Tableau的，定义C[i][j] = A[i] + B[j], 则矩阵C
: 的每行每列都是严格升序排列的，所以C是一个Young Tableau
: 虽然C让问题看去很直观，但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
: 个元素的吧？或许原题可以转换为这个新问题，但能找到一个更巧妙的方法，其复杂度
: 小于这个新问题? 也就是原问题和新问题，不是等价的。
| j**l
发帖数: 2911 | 13 A = {1, 2, 3, 4};
B = {5, 6, 7, 8};
应该输出{6, 7, 7, 8}
为何输出{6, 7, 8, 9}?
【在 S*******n 的大作中提到】
: 你这个题和mergeSort里面那个merge函数有点相似
: 如果题目的意思是A(B)里面的数不能和A(B)自身的数配对的话 这个题应该很好解阿
: 总的运算应该还是n..因为只找n个..
: vector(int) vecForResult=vector(n,0);
: vecForResult[0]=A[0]+B[0];
: int i=1;
: int indexA=0,indexB=0;
: while(i: {
: bool isMoveB= A[indexA]+B[indexB+1]<= A[indexA+1]+B[indexB];
| h**k
发帖数: 3368 | 14 算法不对，简单的说你这个算法无法比较
A[i1]+B[j1] 和 A[i2]+B[j2], if i1>i2 and j1j2.
【在 S*******n 的大作中提到】
: 你这个题和mergeSort里面那个merge函数有点相似
: 如果题目的意思是A(B)里面的数不能和A(B)自身的数配对的话 这个题应该很好解阿
: 总的运算应该还是n..因为只找n个..
: vector(int) vecForResult=vector(n,0);
: vecForResult[0]=A[0]+B[0];
: int i=1;
: int indexA=0,indexB=0;
: while(i: {
: bool isMoveB= A[indexA]+B[indexB+1]<= A[indexA+1]+B[indexB];
| h**k
发帖数: 3368 | 15 恩，直接用heap可以实现O(nlogn)
这个和是一个partial order，(x,y)表示A[x]+B[y]，则
从(0,0)开始，把(0,0)存入heap of size n,
输出heap中的最大值，然后把(0,1)和（1，0）放入heap，再输出最大值。
suppose the maximum element in the heap is (i,j)，remove it and insert( i+1,
j) and (i,j+1) into the heap. Count the output number.
有个问题，(i,j)可能会被放入heap两次，解决方法，
给每个(i,j)设一个counter,initial value = 0, every time we want to put (i,j)
into the heap, check the counter's value, if it = 0, just increase it by 1,
otherwise put it into the heap;
【在 Z*****Z 的大作中提到】
: Young Tableau的情况可以用最小堆做到nlgn吗？
: btw:数组可以转化到YT，但是YT不一定能转化回去吧？
:
: C
: 小n
| a*s
发帖数: 425 | 16 这个问题，我可以想到的最有效的方法是
先找最小的pair,
比如
A=[1,2,3,4]
B=[5,6,7,8]
然后最小的肯定是A 和 B的第一个元素相加，
然后，就相当于
找
A1=[2,3,4]
B1=[5,6,7,8]
OR
A2=[1,2,3,4]
B2=[6,7,8]
这两个组的最小，
有点像二分树的情况，
一个pair，共有n^2个pair。每个pair对两个元素求和，找出和最小的n个pair。
每行每列都是严格升序排列的，所以C是一个Young Tableau。问题化归为，如何在一个
Young Tableau中找到前n个最小元素?
实际上，矩阵C这个Young Tableau是比较特殊的，我们注意到每一行的增量相同，每一
列的增量也相同。所以如果不附加这个特性到Young Tableau, 则原问题和新问题不是
等价的。
问题，应该是等价的。
【在 j**l 的大作中提到】
: A = {1, 2, 3, 4};
: B = {5, 6, 7, 8};
: 应该输出{6, 7, 7, 8}
: 为何输出{6, 7, 8, 9}?
|
|
