codeforces B. Multitasking 解题报告

题目链接：http://codeforces.com/problemset/problem/384/B

题目意思：给出n个数组，每个数组包括m个数字，当k = 0 时，需要把n个数组都按照从小到大的顺序排列，k = 1则把n个数组里面的数字按照从大到小的顺序排列。

　　直接模拟即可，不过有个地方注意下是可以减少工作量的，当处理第 i 行的时候，不再需要移动前 i - 1 行的数组下标。因为前 i - 1行的数组都排好序了。

Time	Memory

46 ms

500 KB

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int maxm =  + ;

 int a[maxn][maxm];

 int ans[][];

 int main()

 {

     int i, j, l, n, m, k, tj, cnt;

     while (scanf("%d%d%d", &n, &m, &k) != EOF)

     {

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

         {

             for (j = ; j <= m; j++)

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

         }

         cnt = ;

         for (i = ; i <= n; i++)  // n 行

         {

             for (j = ; j < m; j++)  // m 列

             {

                 tj = j;

                 int tmp = a[i][j];

                 for (l = j+; l <= m; l++)

                 {

                     if (tmp > a[i][l] && k ==  || tmp < a[i][l] && k == )

                     {

                         tmp = a[i][l];    // 找出第 i 行中第 j 个最少的数

                         tj = l;

                     }

                 }

                 if (j != tj)

                 {

                     swap(a[i][tj], a[i][j]);   // 找完之后要交换

                     if (k == )

                     {

                         ans[cnt][] = j;

                         ans[cnt][] = tj;

                     }

                     else

                     {

                         ans[cnt][] = tj;

                         ans[cnt][] = j;

                     }

                     cnt++;

                     for (l = i+; l <= n; l++)   // 处理第i+1 ~ n 行的数组

                     {

                         if (a[l][j] > a[l][tj] && k ==  || a[l][j] < a[l][tj] && k == )

                             swap(a[l][j], a[l][tj]);

                     }

                 }

             }

         }

         printf("%d\n", cnt);

         for (i = ; i < cnt; i++)

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

     }

     return ;

 }

解法二：堪称暴力中的暴力！！内存都省了

Time	Memory

78 ms

0 KB

k = 0：从小到大排列。意味着所有数组中的第一个数是最小的！这个最小的数如何找？无非就在该行中的某一个数里面。由于不确定在哪里，但用两重循环势必能找出，于是就有了以下简单的方法：对于i = 1，a[i] 可能不是最小的数，于是不断地跟a[i+1], a[i+2], ..., a[m] 比较，即找出排在第一个的数输出 1, 2; 1, 3; ...; 1, m 即可，这样能能保证每个数组都能找出最小的数。第二个最小的数就是2, 3; 2, 4; ...; 2, m了，后面的依次类推。但主要题目中说的，当第 i 个位置的 value > 第 j 个位置的 value 才能交换这个条件。k = 1 则是2, 1; 3, 1; ...; m 1 输出。

 #include <iostream>

 using namespace std;

 int main()

 {

     int n, m, k, i, j;

     while (cin >> n >> m >> k)

     {

         for (i = ; i < n * m; i++)

             cin >> j;

         cout << m * (m - ) /  << endl;

         for (i = ; i < m; i++)

         {

             for (j = i+; j <= m; j++)

             {

                 if (!k)

                     cout << i << " " << j << endl;

                 else

                     cout << j << " " << i << endl;

             }

         }

     }

     return ;

 }

巴特西

codeforces B. Multitasking 解题报告

最新文章

热门文章