正经题解｜买零食

题目分析

有 $n$ 件商品，买一件物品可以免费再拿一件，问买完所有的商品最少花费多少钱。
贪心策略，每次只买剩下中最便宜那个即可，可以先对价格排序，前 $\lceil\frac{n}{2}\rceil$ 的价格的和即为答案。

AC 代码

#include<bits/stdc++.h>
using namespace std;

int s[10000005]; 
int main()
{
	int n;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++ )
	{
		cin >> s[i];
	}

    sort(s + 1, s + 1 + n); 

    if(n % 2) n++;
    n /= 2;

    long long sum = 0 ;
    for(int i = 1 ; i <= n ; i++) {
        sum += s[i];
    }

    cout << sum << endl; 
    
    return 0;
}

现在，数组下标从 1 开始读取输入，排序函数也正确地排序了数组元素。

复杂度

排序加求和，$O(n \cdot log_{n} + n)$。