题目说明：有k种速度，种类1的个数为n1， 种类 2的个数为n2……种类k的个数为nk。对种类进行排序，使得变化的次数最大。eg:
input:
2
2 3
output is not:
1 2 1 2 2
output is:
2 1 2 1 2
题目解析：对所有n进行降序排序，把每种种类保存在一维数组中，利用sub2inedx操作（类似于matlab操作）把二维数组坐标用index表示并输出对应一维数组中的数。
二维数组说明：为了变换次数最大，把最大的种类放在第一列，行数为最大的个数，然后按降序升序一起从上往下从左往右填充剩下的种类并输出。
该算法精髓：sub2index
Problem analysis English version:
- Sort signs in descending order
- Using one dimensional array to story type.
- Output two dimension matrix using sub2index function likely in Matlab program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<iostream> #include<algorithm> using namespace std; struct Sign { int type, number; }sign[20000]; struct Position { int x, y; }; int f(Sign& a, Sign& b) { return a.number > b.number; } int sub2index(struct Position position, int width) { return position.y * width + position.x; } int main() { int k; cin >> k; int array[20000] = { 0 }; for (int i = 0; i < k; i++) { cin >> sign[i].number; sign[i].type = i + 1; } sort(sign, sign + k, f); int temp = 0; for (int i = 0; i < k; i++) { for (int j = 0; j < sign[i].number; j++) { array[temp] = sign[i].type; temp++; } } struct Position position; int max = (temp - 1)/ sign[0].number; for (int i = 0; i < sign[0].number; i++) { position.x = i; for (int j = 0; j <= max; j++) { position.y = j; int number = array[sub2index(position, sign[0].number)]; if (number != 0) cout << number << " "; } } return 0; } |
浙公网安备 33010902002953号