火星人
題目來源：NOIP2004普及組
時間限制：\(1000ms\) 記憶體限制：\(128mb\)
題目描述
人類終于登上了火星的土地并且見到了神秘的火星人，
人類和火星人都無法理解對方的語言，但是我們的科學家發明了一種用數字交流的方法，
這種交流方法是這樣的，首先，火星人把一個非常大的數字告訴人類科學家，科學家破解這個數字的含義后，再把一個很小的數字加到這個大數上面，把結果告訴火星人，作為人類的回答，
火星人用一種非常簡單的方式來表示數字——掰手指，
火星人只有一只手，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為 \(1, 2, 3, …\) ，
火星人的任意兩根手指都能隨意交換位置，他們就是通過這方法計數的，
一個火星人用一個人類的手演示了如何用手指計數，
如果把五根手指——拇指、食指、中指、無名指和小指分別編號為 \(1\) , \(2\) , \(3\) , \(4\) 和 \(5\) ，當它們按正常順序排列時，形成了5位數 \(12345\) ，當你交換無名指和小指的位置時，會形成5位數 \(12354\) ，當你把五個手指的順序完全顛倒時，會形成 \(54321\) ，在所有能夠形成的120個5位數中， \(12345\) 最小，它表示 \(1\) ； \(12354\) 第二小，它表示 \(2\) ； \(54321\) 最大，它表示 \(120\) ，
下表展示了只有3根手指時能夠形成的 \(6\)個3位數和它們代表的數字：
三位數 \([123, 132, 213, 231, 312, 321]\)
分別代表的數字 \([1, 2, 3, 4, 5, 6]\)
現在你有幸成為了第一個和火星人交流的地球人，
一個火星人會讓你看他的手指，科學家會告訴你要加上去的很小的數，
你的任務是，把火星人用手指表示的數與科學家告訴你的數相加，并根據相加的結果改變火星人手指的排列順序，
輸入資料保證這個結果不會超出火星人手指能表示的范圍，
輸入格式
輸入包括三行，第一行有一個正整數 \(N\) ，表示火星人手指的數目，
第二行是一個正整數 \(M\) ，表示要加上去的小整數，
下一行是有 \(N\) 個整數的一個排列，用空格隔開，表示火星人手指的排列順序，
輸出格式
輸出只有一行，這一行含有 \(N\) 個整數，表示改變后的火星人手指的排列順序，
每兩個相鄰的數中間用一個空格分開，不能有多余的空格，
資料范圍
\(1 ≤ N ≤ 10000\) ,
\(1 ≤ M ≤ 100\)
樣例輸入
5
3
1 2 3 4 5
樣例輸出
1 2 4 5 3
解題思路
按照題目給的 \(3\) 個手指的方案，發現順序為字典序全排列，由字典序從小到大排列，第幾個序串列示數字幾，
原始序列代表的數加上m，可以解釋為，原始序列之后的第m個比它大的序列，
在c++中，模板庫里已經為我們寫好了求字典序+1的函式，next_permutation()，只需要呼叫m次這個函式，就可以得到答案，
java中沒有此函式，所以需要手動寫，
解題代碼-C++
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int *a = new int[n];
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
while(m--)
{
next_permutation(a, a + n);
}
for(int i = 0; i < n; i++)
{
cout << a[i] << ' ';
}
return 0;
}
解題代碼-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
}
input.close();
//C++STL庫algorithm中使用next_permutation(a,a+n)可以得到比原序列字典序大1的序列
//while (m--) {
// next_permutation(a,a+n);
//}
while (m > 0) {
int k = n - 2;
while (a[k] > a[k + 1]) {
k--;
}
int t = k + 1;
while (t + 1 < n && a[t + 1] > a[k]) {
t++;
}
int temp = a[t]; //交換a[k]與a[t]的值，swap(a[k], a[t])
a[t] = a[k];
a[k] = temp;
int left = k + 1, right = n - 1;
while (left < right) { //反轉序列從k+1到n-1的項，reverse(a + k + 1, n)
temp = a[left];
a[left] = a[right];
a[right] = temp;
left++;
right--;
}
m--;
}
for (int i = 0; i < n; i++) {
System.out.printf("%d ", a[i]);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253429.html
標籤：其他
上一篇：2021寒假每日一題《合唱隊形》