1744번: 수 묶기

https://www.acmicpc.net/problem/1744


$O(n)$

먼저 수들을 정렬하자.

작은 수부터 1보다 작을 때까지만 두 개씩 묶는다.
큰 수부터 1보다 클 때까지만 두 개씩 묶는다.
나머지 수들은 그대로 둔다.

#include<cstdio>
#include<algorithm>
using namespace std;
int a[10000], n, r;
int main() {
    scanf("%d", &n);
    int i, j;
    for (i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    for (i = 0; i < n - 1 && a[i + 1] < 1; i += 2) r += a[i] * a[i + 1];
    for (j = n - 1; j&&a[j - 1] > 1; j -= 2) r += a[j] * a[j - 1];
    for (; i <= j; i++) r += a[i];
    printf("%d", r);
    return 0;
}