同じ配列を使って2回ソートをしない方がいい理由。

結論

一度ソートした配列をもう一度ソートすると定義してない値が入ってしまうから。

注意

AtCoderの
・abc103_A - Task Scheduling Problem
・abc291_B - Trimmed Mean
のネタバレあり。

方針

[1] 標準入力からnを受け取る。
[2] n * 5をn5と定義し、xを配列で受け取る。
[3] xを配列を昇順ソートする。
[4] 昇順ソート後、前から2番目までの整数をnewxという配列にコピーする。
[5] newxとxを比較し、値が異なる時にneoxの配列にxの配列をコピーする。
[6] neox配列を降順ソートする。← ここで定義してない値が入っている事に気づく。
[7] 降順ソート後、前から2番目までの整数をhighxという配列にコピーする。
[8] highxとneoxを比較し、値が異なる時にlastxの配列にneoxの配列をコピーする。
[9] lastxの配列の値を全て足し算する。
[10] 足し算の結果を小数点に対応できるようにdouble型かfloat型にする。
[11] 足し算した回数も小数点に対応できるようにdouble型かfloat型にする。
[12] lastxの足し算した合計 / 足し算した回数で割り算する。

※[6] neox配列を降順ソートする。から思考停止したので[6]以降は未実施。

2回ソートをしない方がいいと気づくまでのコード

前提条件
・この問題の入力例2で話を進めます。

#include <stdio.h>
int	main(void)
{
	int	n;//5N 人の審査員

	scanf("%d",&n);
	printf("n=%d\n",n);

	int n5 = n * 5;
	printf("n5=%d\n", n5);

	int x[n5];
	for (int i = 0; i < n5; i++)
	{
		scanf("%d", &x[i]);
		// printf("%d ", x[i]);
	}
	//ここから昇順ソート
	int i;
	int j;
	int tmp = 0;
	for (i = 0; i < n5; i++)
	{
		for (j = i + 1; j < n5; j++)
		{
			if (x[i] > x[j])
			{
				tmp = x[i];
				x[i] = x[j];
				x[j] = tmp;
			}
		}
	}
	//	並べ替え結果の表示
	for ( i= 0 ; i < n5; i++)
	{
		printf("x[i]=%d ", x[i]);
	}
	printf("\n");
	//低い点をつけたn(2)人を見つけて低い点の人たちをnewxにコピーする。
	int newx[n + 1];
	//配列を昇順にしたので前からn(2)番目までをnewxにコピーする。
	//
	for (int i = 0; i < n; i++)
	{
		// printf("%d ",x[i]);
		newx[i] = x[i];
		printf("newx[i]=%d ", newx[i]);
	}
	printf("\n");
	//前からn番目(低い点)以外の人たちをneox配列にコピーする。
	int neox[n5 - n];
	for (int i = 0; i < n5; i++)
	{
		if(newx[i] != x[i]){
			neox[i] = x[i];
			printf("neox[i]=%d ", neox[i]);
		}
	}
	printf("\n");
	//ここから降順ソート
	//一度ソートした配列をもう一度ソートすると定義してない値が入ってしまう。
	j = 0;
	tmp = 0;
	for (i = 0; i < n5 ; i++)
	{
		for (j = i + 1; j < n5; j++)
		{
			if (neox[i] < neox[j])
			{
				tmp = neox[i];
				neox[i] = neox[j];
				neox[j] = tmp;
			}
		}
	}
	//	並べ替え結果の表示
	for (i = 0 ; i < n5 - n; i++)
	{
		printf("neox[i]=%d ", neox[i]);
	}
	printf("\n");
	// 高い点をつけたn人を見つけて高い点の人たちをhighxにコピーする。
	// int highx[n];
	// for (int i = 0; i < n; i++)
	// {
	// 	// printf("%d ",x[i]);
	// 	highx[i] = neonewx[i];
	// 	printf("highx[i]=%d ", highx[i]);
	// }
	// printf("\n");
	// //高い点以外の人たちをneox配列にコピーする。
	// int last_x[n5];
	// for (int i = 0; i < n5 - n * n; i++)
	// {
	// 	if(highx[i] != neox[i]){
	// 		last_x[i] = highx[i];
	// 		printf("last_x[i]=%d ", last_x[i]);
	// 	}
	// }
	// printf("\n");
	return (0);
}

実行結果

n=2
n5=10
x[i]=3_x[i]=3_x[i]=3_x[i]=4_x[i]=5_x[i]=6_x[i]=7_x[i]=8_x[i]=99_x[i]=100_(trailing whitespace)
newx[i]=3_newx[i]=3_(trailing whitespace)
neox[i]=3_neox[i]=4_neox[i]=5_neox[i]=6_neox[i]=7_neox[i]=8_neox[i]=99_neox[i]=100_(trailing whitespace)
neox[i]=32766_neox[i]=100_neox[i]=99_neox[i]=8_neox[i]=7_neox[i]=6_neox[i]=5_neox[i]=4(trailing whitespace)
neox[i]=32766この値がどうしても入ってきてしまうので先に進めなかった。

ACしたコード

#include <stdio.h>
int	main(void)
{
	int	n;//5N 人の審査員

	scanf("%d",&n);
	// printf("n=%d\n",n);

	int n5 = n * 5;
	// printf("n5=%d\n", n5);

	int x[n5];
	for (int i = 0; i < n5; i++)
	{
		scanf("%d", &x[i]);
		// printf("%d ", x[i]);
	}
	//ここから昇順ソート
	int i;
	int j;
	int tmp = 0;
	for (i = 0; i < n5; i++)
	{
		for (j = i + 1; j < n5; j++)
		{
			if (x[i] > x[j])
			{
				tmp = x[i];
				x[i] = x[j];
				x[j] = tmp;
			}
		}
	}
	//	並べ替え結果の表示
	for (i = 0 ; i < n5; i++)
	{
		// printf("x[i]=%d ", x[i]);
	}
	//ここから写経
	float avg=0.0;
	for(i = n; i < n5 - n; i++){
    avg += x[i];
	}
	// printf("\n");

  	printf("%f\n",avg /(n5 - n * 2));
	return (0);
}

実行結果

//実行結果
5.500000
//出力例 2 
5.500000000000000

理解したこと

・足し算する範囲をnからn5 - nにすれば足し算したい範囲を指定できる。

参考にした記事

その他

過去の自分に助けてもらった回数

1回目:2023/02/27
2回目:2023/03/05 abc103_A - Task Scheduling Problem ▷ 詳細あり