ABC#006 D問題

とりあえず競プロ問題一日一問は有限実行中!!

#include <iostream>
#include <cstdio>

#define rep(i,n) for( int i = 0; i < n; i++)

using namespace std;

int n,card[30000];


int main()
{
	cin >> n;
	int retu[30000];
	rep(i,n){
		retu[i] = 1000000;
		cin >> card[i];
	}
	rep(i,n)
	{
		rep(j,n)
		{
			if( card[i] < retu[j] ){
				retu[j] = card[i];
				goto loop;
			}
		}
loop:;
	}
	int count = 0;
	rep(i,n)
	{
		if( retu[i] != 1000000 )
			count++;
	}
	cout << n - count << endl;
	return 0;
}

gotoだ!!!!殺せ!!!!みたいなのは置いといて

ABCの解説スライドがとても優しくて解けた。

解説見ながらだけどD問題解けたの初めてな気がする!嬉しい!

二重ループだから O(n^2)になるのかな?と思うと

そうではないっぽい。

計算量むずい。