[白俊/C+]1377号:気泡セット

📁 質問する

💭 最初のプール(タイムアウト)

#include <iostream>
using namespace std;

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main()
{
	int N;
	cin >> N;

	int* A = new int[N];

	for (int k = 1; k < N+1; k++) {
			cin >> A[k];
	}

	bool changed = false;

	for (int i = 1; i <= N + 1; i++) {
			changed = false;
			for (int j = 1; j <= N - i; j++) {
					if (A[j] > A[j + 1]) {
							changed = true;
							swap(A[j], A[j + 1]);
					}
			}
			if (changed == false) {
					cout << i << '\n';
					break;
			}
	}
	return 0;
}

🤍 成功!

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

int main()
{
    int n;
    cin >> n;

    vector<pair<int, int>> v;
    int val;

    for (int idx = 0; idx < n; idx++) {
        cin >> val;
        v.push_back(pair<int, int>(val,idx));
    }

    sort(v.begin(), v.end());

    int r = 0;
    for (int i = 0; i < n; i++) {
        if (v[i].second - i > r) {
            r = v[i].second - i;
        }
    }
    
    cout << r + 1 << '\n';

    return 0;
}

>v(n)なお、n個の値はいずれも0に初期化する

見た目が簡単なので見間違えやすく、結局タイムアウトになってしまい、本当に慌ただしくて・・・😱
そうですね.こんなに簡単にはできません.最初は泡のソートにすっかり惹かれていたので、他の方法を考え出すのは難しいです.ほほほ
また,実現アルゴリズムは容易であるが,c++を熟知していないため,ソースコードで実現することは困難である.

📚 参考になるブログ

ベクトルの使い方-https://blockdmask.tistory.com/70

pair用法-https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=chansung0602&logNo=221006857783

vectorとpairを使用

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ckdgus1433&logNo=221666899817

https://godog.tistory.com/entry/c-vector-and-pair-%EC%82%AC%EC%9A%A9