[伯俊/BOJ]15082+1販促[Silver 4]
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;
}
Reference
この問題について([伯俊/BOJ]15082+1販促[Silver 4]), 我々は、より多くの情報をここで見つけました https://velog.io/@jychan99/백준BOJ11508.-21-세일Silver-4시간초과テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol