【2021年度訓練聯盟熱身訓練賽第五場】
H In-place Sorting （貪心 字典序比較）
【題目描述】
Woe is you – for your algorithms class you have to write a sorting algorithm, but you missed the relevant lecture! The subject was in-place sorting algorithms, which you deduce must be algorithms that leave each input number in its place and yet somehow also sort the sequence.
Of course you cannot change any of the numbers either, then the result would just be a difffferent sequence. But then it hits you: if you flflip a 6 upside-down, it becomes a 9, and vice versa! Certainly no one can complain about this since you changed none of the digits! The deadline to hand in the exercise is in fifive hours. Try to implement this sorting algorithm before then!
【輸入描述】
The input consists of:
? A line with an integer n (2 ≤ n ≤ 10 000), the number of integers in the input sequence.
? n lines, the ith of which contains a positive integer xi (1 ≤ xi ≤ 1018), the ith number of the sequence.
【輸出描述】
If the sequence cannot be sorted non-decreasingly by flipping some number 6 or 9 in input 1, output “not possible”. Otherwise, output “possible” followed by the sorted sequence - each number on its own line.
If there is more than one valid solution, please output the smallest sequence.
【示例1】
輸入
4
9
7
7
9
輸出
possible
6
7
7
9
【示例2】
輸入
4
97
96
66
160
輸出
possible
67
69
69
160
【示例3】
輸入
3
80
97
79
輸出
impossible
【示例4】
輸入
2
197
166
輸出
possible
167
169
【解題思路】
本題輸入一組數字，我們可以每個數字當中的6和9互相替換，問能否進行一些替換以后，使得所有數字遞增（可以相等），
顯然我們可以采取貪心的策略，
這里我們用字串型別來存取數字，方便進行替換操作以及字典序比較，
首先將第一個數字當中的所有9都替換成6，使其最小，
然后從第二個數字開始往后處理：
如果當前數字長度比前一個數字短，那么顯然不可能滿足遞增，直接輸出impossible并結束，
如果當前數字長度比前一個數字長，那么顯然已經滿足遞增，我們將數字當中的所有9都替換成6，使其最小，然后進入處理下一個數字，
如果當前數字長度和前一個數字一樣長，那么我們要使其大于前一個數字但又盡可能地小，
首先判斷是否有可能滿足遞增，我們把數字當中所有的6都替換成9，如果替換以后的數字還比前一個數字小，那么顯然不可能滿足遞增，輸出impossible并結束，
如果替換以后的數字滿足比前一個數字大，但它還不一定是最小的，我們逐位檢查能否把數字中的9替換成6，使其盡可能得小，這就是貪心的最優策略，
【AC代碼】
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
string s[10005];
cin>>n;
for(int i=0;i<n;i++)
cin>>s[i];
int len=s[0].length();
for(int j=0;j<len;j++)
if(s[0][j]=='9')
s[0][j]='6';//將第一個數的所有9換成6
int flag=1;
for(int i=1;i<n;i++)
{
len=s[i].length();
if(len<s[i-1].length())
{
flag=0;
break;
}//如果長度比前一個數小，則不可能
if(len>s[i-1].length())
{
for(int j=0;j<len;j++)
if(s[i][j]=='9')
s[i][j]='6';
continue;
}//如果長度比前一個數大，則將所有9換成6即可
for(int j=0;j<len;j++)
if(s[i][j]=='6')
s[i][j]='9';
if(s[i-1].compare(s[i])>0)
{
flag=0;
break;
}//如果將所有6換成9還比前一個數小，則不可能
for(int j=0;j<len;j++)
{
if(s[i][j]=='9')
{
s[i][j]='6';
if(s[i-1].compare(s[i])>0)
s[i][j]='9';
}
}//從前往后試把9換成6
/*
for(int j=len-1;j>=0;j--)
{
if(s[i][j]=='9')
{
s[i][j]='6';
if(s[i-1].compare(s[i])>0)
s[i][j]='9';
}
}//從后往前試把9換成6
*///這個回圈不要也行，因為完整遍歷過一遍就已經能夠保證是當前的最優解了
}
if(flag==0)
cout<<"impossible"<<endl;
if(flag==1)
{
cout<<"possible"<<endl;
for(int i=0;i<n;i++)
cout<<s[i]<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/275503.html
標籤：其他