[伯俊/BOJ]15082+1販促[Silver 4]


  • 2+1販促
  • 質問元:https://www.acmicpc.net/problem/11508
    code
    #include <stdio.h>
    void QuickSort(int arr[],int start,int end)
    {
    	if (start >= end)
    		return;
    	int piv = start, 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, C[100000] = { 0 }, i, total = 0;
    	scanf("%d", &N);
    	for (i = 0; i < N; i++)
    		scanf("%d", &C[i]);
    	QuickSort(C, 0, N-1);
    	for (i = 0; i < N; i++)
    		if (i % 3 != 2)
    			total += C[i];
    	printf("%d", total);
    	return 0;
    }
    最大の割引を得るには、降順にソートし、3番目のインデックス以外のすべての値を加算します.
    (3つ目は無料なので)
    でもいつもタイムアウト...
    C++で解決しました.アルゴリズムは同じです.
    code
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
    	ios::sync_with_stdio(false);
    
    	int N, C[100000] = { 0 }, i, total = 0;
    
    	cin >> N;
    	for (i = 0; i < N; i++)
    		cin >> C[i];
    
    	sort(C, C + N, greater<>());
    
    	for (i = 0; i < N; i++)
    		if (i % 3 != 2)
    			total += C[i];
    
    	cout << total;
    
    	return 0;
    }