[伯俊/BOJ]16471小数[Silver 5]

1497 ワード

  • 小数
  • 質問元:https://www.acmicpc.net/problem/16471
    code
    #include <stdio.h>
    void QuickSort(int *arr, int start, int end)
    {
    	if (start >= end)
    		return;
    	int piv = start;
    	int left = start + 1, right = end, temp;
    	while (left <= right)
    	{
    		while (left <= end && arr[left] <= arr[piv])
    			left++;
    		while (right > start && arr[right] >= arr[piv])
    			right--;
    		if (left > right)
    		{
    			temp = arr[right];
    			arr[right] = arr[piv];
    			arr[piv] = temp;
    		}
    		else
    		{
    			temp = arr[left];
    			arr[left] = arr[right];
    			arr[right] = temp;
    		}
    	}
    	QuickSort(arr, start, right - 1);
    	QuickSort(arr, right + 1, end);
    }
    int main()
    {
    	int N, i, cnt = 0;
    	int Ju[100000] = { NULL }, Sa[100000] = { NULL };
    	scanf("%d", &N);
    	for (i = 0; i < N; i++)
    		scanf("%d", &Ju[i]);
    	for (i = 0; i < N; i++)
    		scanf("%d", &Sa[i]);
    	QuickSort(Ju, 0, N - 1);
    	QuickSort(Sa, 0, N - 1);
    	for (i = 0; i < N / 2 + 1; i++)
    		if (Ju[i] < Sa[N / 2 + i])
    			cnt++;
    	if (cnt >= (N + 1) / 2)
    		printf("YES");
    	else
    		printf("NO");
    	return 0;
    }
    私がvisualstudioで作ったコードを見て、Bubbleソート、挿入ソート、選択ソートはすべてやりました.バックグラウンドでタイムアウトが発生したので、時間の複雑さが最小の高速ソートでいいです.