hdu oj 1872
4060 ワード
安定したソート
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7120 Accepted Submission(s): 2626
Problem Description
高速ソートは不安定なソート方法であることはよく知られています.
配列に現れる任意のa[i],a[j](i)について
ある大学の学生募集弁公室は、受験生の名前と受験生の成績を記録した成績リストを取得し、あるソートアルゴリズムを使用して成績を減算してソートしました.今、このソートアルゴリズムが正しいかどうかを判断してください.もし正しいならば、そのソートアルゴリズムが安定しているかどうかを判断してください.
Input
このテーマには複数の入力が含まれています.ファイルが終わるまで処理してください.
各グループのデータについて、最初の行には正の整数N(0の次にN行があり、各行には受験生の名前を表す文字列(長さ50を超えず、'a'~'zのみを含む)と、受験生の点数(500未満)を表す整数があります.名前と成績はスペースで区切られています.
次にN行があり、上記のリストがあるソートアルゴリズムを経て生成されたシーケンスです.フォーマットは同じです.
Output
各グループのデータについて、アルゴリズムが正しく安定している場合は、1行に「Right」を出力します.アルゴリズムが正しいが安定していない場合は、1行に「Not Stable」を出力し、次に正確に安定したソートのリストを出力します.フォーマットは入力と同じです.このアルゴリズムが間違っている場合は、1行に「Error」を出力しますを選択し、次に、正しく安定したソートのリストを出力します.フォーマットは入力と同じです.
なお,本問題では,このソートアルゴリズムが誤りであることを考慮しないが,結果は正しいという意外な状況である.
Sample Input
acコード:
考え:
優先度の問題を考慮していないで、もし問題が与えるシーケンスならば、iの位置は1つの不安定な並べ替え点があって、forは直接breakして、だからiの後ろに現れる誤った並べ替え点は無視して、この時私が判定したプログラムはerrorではなくnot stableで、このような問題カードに何時間も聞かれるのは本当につらくて、後でやはり怠けないほうがいいで、おとなしく2つの標識位です.
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7120 Accepted Submission(s): 2626
Problem Description
高速ソートは不安定なソート方法であることはよく知られています.
配列に現れる任意のa[i],a[j](i)について
ある大学の学生募集弁公室は、受験生の名前と受験生の成績を記録した成績リストを取得し、あるソートアルゴリズムを使用して成績を減算してソートしました.今、このソートアルゴリズムが正しいかどうかを判断してください.もし正しいならば、そのソートアルゴリズムが安定しているかどうかを判断してください.
Input
このテーマには複数の入力が含まれています.ファイルが終わるまで処理してください.
各グループのデータについて、最初の行には正の整数N(0の次にN行があり、各行には受験生の名前を表す文字列(長さ50を超えず、'a'~'zのみを含む)と、受験生の点数(500未満)を表す整数があります.名前と成績はスペースで区切られています.
次にN行があり、上記のリストがあるソートアルゴリズムを経て生成されたシーケンスです.フォーマットは同じです.
Output
各グループのデータについて、アルゴリズムが正しく安定している場合は、1行に「Right」を出力します.アルゴリズムが正しいが安定していない場合は、1行に「Not Stable」を出力し、次に正確に安定したソートのリストを出力します.フォーマットは入力と同じです.このアルゴリズムが間違っている場合は、1行に「Error」を出力しますを選択し、次に、正しく安定したソートのリストを出力します.フォーマットは入力と同じです.
なお,本問題では,このソートアルゴリズムが誤りであることを考慮しないが,結果は正しいという意外な状況である.
Sample Input
3 aa 10 bb 10 cc 20 cc 20 bb 10 aa 10 3 aa 10 bb 10 cc 20 cc 20 aa 10 bb 10 3 aa 10 bb 10 cc 20 aa 10 bb 10 cc 20
Sample Output
Not Stable cc 20 aa 10 bb 10 Right Error cc 20 aa 10 bb 10
死活都不能ac的代码：
#include
#include
#include
#include
#include
using namespace std;
bool compare(const pair&a,const pair&b) {
return a.second > b.second;
}
void main() {
int n;
while (cin>>n) {
vector>s(n,pair("",0));
bool flag = true;
int k;
for (int i = 0; i < n; i++)
cin >> s[i].first >> s[i].second;
vector>a(n, pair("", 0));
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
stable_sort(s.begin(),s.end(),compare);
for (k = 0; k < n; k++) {
if (s[k].second != a[k].second) {
flag = false;
break;
}
else if (s[k].first != a[k].first)
break;
}
if (k==n)
cout << "Right" << endl;
else {
if (flag)
cout< acコード:
#include
#include
#include
#include
#include
using namespace std;
bool compare(const pair&a,const pair&b) {
return a.second > b.second;
}
void main() {
int n;
while (cin>>n) {
vector>s(n,pair("",0));
bool flag1 = true;
bool flag2 = true;
for (int i = 0; i < n; i++)
cin >> s[i].first >> s[i].second;
vector>a(n, pair("", 0));
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
stable_sort(s.begin(),s.end(),compare);
for (int k = 0; k < n; k++) {
if (s[k].second != a[k].second)
flag1 = false;
else if (s[k].first != a[k].first)
flag2 = false;
}
if (flag1&&flag2)
cout << "Right" << endl;
else {
if (!flag1)
cout< 考え:
優先度の問題を考慮していないで、もし問題が与えるシーケンスならば、iの位置は1つの不安定な並べ替え点があって、forは直接breakして、だからiの後ろに現れる誤った並べ替え点は無視して、この時私が判定したプログラムはerrorではなくnot stableで、このような問題カードに何時間も聞かれるのは本当につらくて、後でやはり怠けないほうがいいで、おとなしく2つの標識位です.