SRM531 easy(250) - avrmicom @ ウィキ

約35分

問題概要

昇順にソートされていない数列の中で、最も辞書式順が早いものを答える問題。

解法

配列をソートしてから、末尾の一部を崩せばできる。
ソートされていない配列を返せばいいものだと勘違いして、時間かかかってしまった。

解答

#include <iostream>
#include <vector>
using namespace std;

class UnsortedSequence{
public:
	vector <int> getUnsorted(vector <int> s){
		vector<int> vec;
		if(s.size()<=1)
			return vec;
		for(int i=0; i<s.size()-1; i++){
			for(int j=i+1; j<s.size(); j++){
				if(s[i]>s[j]){
					int tmp=s[i];
					s[i]=s[j];
					s[j]=tmp;
				}
			}
		}
		
		for(int i=0; i<s.size(); i++){
			cout << s[i] << " ";
		}
		
		for(int i=s.size()-1; i>0; i--){
			if(s[i-1]<s[i]){
				int tmp=s[i-1];
				s[i-1]=s[i];
				s[i]=tmp;
				return s;
			}
		}
		return vec;
	}
};