[算法]数列排序

firstddf

1. 
   
2.    B   90  29  14   7   5   2
   
3. A
   
4. 100   190 129 114 107 105 102
   
5.   99   189 128 113 106 104 101
   
6.   98   188 127 112 105 103 100
   
7.   86   176 115 100  93  91  88
   
8.   20   110  49  34  27  25  22
   
9.    1    91  30  15   8   6   3
   

复制代码

看一下这个数组，很难找到规律的。

Iambitious

A + B[j] >= A + B[v] u >=i v >=j
这也是我的算法工作的原理。

firstddf

Post by Iambitious
A + B[j] >= A + B[v] u >=i v >=j

P(3,1)=A[3]+B[1]>(5,1)=A[5]+B[1];
P(1,3)=A[1]+B[3]>(1,5)=A[1]+B[5];
这是肯定能确定的
但
P(3,1)和P(1,3)，P(5,1)和P（1,5）怎么确定大小，横向和纵向这种对比是容易的。


我有一个笨的算法（如果数组中元素是非0的正短整数）
P［］中两个元素最小的相差值为1。
P［n+1］  n最大应该为A[0]+B[0];(由于数组是从0开始编号）
但这个我编译始终有错，数组后面的一些元素总出错，不知道是什么原因，会不会是溢出了；

1. 
   
2. #include <stdio.h>
   
3. int main()
   
4. {
   
5.     int p[191];
   
6.     int a[]={100,99,98,86,20,1};
   
7.     int b[]={90,29,14,7,5,2};
   
8.     int i,m,n,s;
   
9.     for (n=0;n<6;n++)
   
10.     {
    
11.         for (m=0;m<6;m++)
    
12.         {
    
13.             s=a[n]+b[m];
    
14.             p[s]=s;
    
15.             printf("s%d,%d\n",s,p[s]);
    
16.         }
    
17.     }
    
18. 
    
19.     for (i=0;i<191;i++)
    
20.     {
    
21.         printf("p%d,%d\n",i,p[i]);
    
22.     }
    
23.     return 0;
    
24. }
    

复制代码

Iambitious

你可以看看败者树的相关知识，有助于你解决这道题。
参看严慰敏所写的数据结构的外排序一章。

Iambitious

你的程序通过编译没有问题，估计你想问的是为什么p数组里面有很多奇怪的值吧，那主要是因为
p数组没有被初始化。

firstddf

多谢指出问题所在，重新调整后的代码

1. 
   
2. #include <stdio.h>
   
3. int main()
   
4. {
   
5.     int p[191];
   
6.     int w[36];
   
7.     int a[]={100,99,98,86,20,1};
   
8.     int b[]={90,29,14,7,5,2};
   
9.     int i,m,n,s,t,x=0;
   
10.     //初始p[]
    
11.     for (i=0;i<191;i++)
    
12.     {
    
13.         p[i]=-1;
    
14.     }
    
15.     //求出a[]+b[]
    
16.     for (n=0;n<6;n++)
    
17.     {
    
18.         for (m=0;m<6;m++)
    
19.         {
    
20.             s=a[n]+b[m];
    
21.             p[s]=s;
    
22.             //printf("p%d,%d\n",s,p[s]);
    
23.         }
    
24.     }
    
25.     // 整理p[]
    
26.     for (i=0;i<191;i++)
    
27.     {
    
28.         if( p[i]!=-1)
    
29.         {
    
30.             //printf("p%d,%d\n",i,p[i]);
    
31.             t=p[i];
    
32.             w[x]=t;
    
33.             printf("w%d,%d\n",x,w[x]);
    
34.             x++;
    
35.         }
    
36.     }
    
37.     return 0;
    
38. }
    

复制代码

Iambitious

昨天做topcoder遇到了一道题，跟这道题有点类似，但是有特殊的地方，解法很有意思，大家考虑考虑。

题目如下：
考虑一个n * n 的矩阵A[1..n][1..n]，A[j] = i * j(1<=i,j<=n)，求第k个最小的A[j]。

数据范围：
1<=n<=100000
1<=k<=min(1000000000, n * n)

要求：

程序在2秒内返回正确结果

例子：
n=3,k=7
A[1..3][1..3]:
1 2 3
2 4 6
3 6 9
result=6

yuhch123

楼上那题，二分答案吧

yuhch123

1. 
   
2. yuhch@localhost ~/tmp $ cat tmp.c
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. long long N, K;
   
6. long long GetAns1(long long x) {
   
7.    long long t = 0, i, j;
   
8.    for (i = 0; i < N; i ++)
   
9.       t += ((j = (x - 1) / (i + 1)) > N ? N : j);
   
10.    return t;
    
11. }
    
12. long long GetAns2(long long x) {
    
13.    long long t = 0, i, j;
    
14.    for (i = 0; i < N; i ++)
    
15.       t += ((j = x / (i + 1)) > N ? N : j);
    
16.    return t;
    
17. }
    
18. int main() {
    
19.    long long f, r, m, t1;
    
20.    freopen("pro.in", "r", stdin);
    
21.    scanf("%lld%lld", &N, &K);
    
22.    f = 0;
    
23.    r = (long long)N * (long long)N;
    
24.    while (1) {
    
25.       m = (f + r) / 2;
    
26.       if ((t1 = GetAns1(m) + 1) <= K && (GetAns2(m)) >= K)
    
27.          break;
    
28.       if (t1 > K)
    
29.          r = m;
    
30.       else
    
31.          f = m + 1;
    
32.    }
    
33.    printf("%lld\n", m);
    
34.    return 0;
    
35. }
    
36. 
    
37. yuhch@localhost ~/tmp $ cat pro.in
    
38. 100000 1000000000
    
39. yuhch@localhost ~/tmp $ time make run
    
40. ./tmp
    
41. 204535821
    
42. 
    
43. real    0m0.207s
    
44. user    0m0.202s
    
45. sys     0m0.002s
    

复制代码

Iambitious

very good!
in truth,

2. import java.util.*;
3. public class ProductsMatrix {
4.     public long nthElement(int n, int k) {
5.          long min = 1;
6.          long max = (long)n * (long)n;
7.          while(min < max){
8.                  long mid = (max + min) / 2;
9.                  long count = 0;
10.                  for(int i = 1; i <= n; i++){
11.                          count += Math.min(n, mid / i);
12.                  }
13.                  if(count < k){
14.                          min = mid + 1;
15.                  }
16.                  else{
17.                          max = mid;
18.                  }
19.          }
20.         return min;
21.     }
22. }

复制代码

is ok