In-place Sorting（逆向思维，数组下标用vector代替）

深藏阁楼爱情的钟 2023-01-19 04:34 101阅读 0赞

https://ac.nowcoder.com/acm/contest/13926/H

题目：给定n个数字，每个数字6和9能互换，输出不减序列，或者输出“impossible”

## 思路：对于每个数字，先把6全换成9； ##

## **换成6**（6比较小，为了输出最小序列），如果换了还是不减序列，则换。   否则   **保持9**，如果保持9还是比之前的数小，输出“impossible” ##

--------------------

例如：  
4  
97  
96  
66  
160

换9

4  
97  
99  
99  
190

依次换6，能换则换

4  
67  
96  
99  
160

**注意：如果不想要数组的下标，则可以使用向量**

vector<ll> a;

#include<bits/stdc++.h>
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    using namespace std;
    
    vector <ll> a;
    string str;
    
    ll fun(string str)
    { 
        ll ans = 0;
        ll cnt = 1;
        for(int i = str.length()-1; i >= 0; i--){ 
            ans += (str[i]-'0')*cnt;
            cnt *= 10;
        }
        return ans;
    }
    
    int main()
    { 
    	int n; cin >> n;
        bool flag = true;
        ll pre = 0;
        rep(i,1,n)
        { 
            cin >> str;
            rep(j,0,str.length()-1) if(str[j]=='6') str[j]='9';
            rep(j,0,str.length()-1){ 
                if(str[j]=='9' && fun(str) >= pre) str[j] = '6';
                if(str[j]=='6' && fun(str) < pre) str[j] = '9';
            }
            if(fun(str) < pre) flag = false;
            else { 
                pre = fun(str);
                a.push_back(pre);
            }
        }
        if(flag == false) { puts("impossible");return 0;}
        puts("possible");
        for(int i = 0; i < a.size(); i++) cout << a[i] << endl;
        return 0;
    }