良神爱购物

NC14401. 良神爱购物

描述

双12马上要来了，良神要备战双12的购物行动，现在已知商家给出的优惠政策如下：

当你每次下单不少于12件物品时，会免去这些物品中价格最低的一件物品的钱，每次下单会有12块钱运费。

现在给出良神购物车所有的物品价格的情况下，请选择相应策略使得购买所有物品，并使付的钱最少，输出最小支付金额。

输入描述

第1行输入一个整数n，代表良神购物车有n件商品。
第2行输入n个整数，第i个整数a[i]代表良神购物车第i件商品的价格。
数据保证：12≤n≤1200，0<a[i]≤1200

输出描述

输出一行，代表良神购买所有物品的最小支付金额。

示例1

输入:

12
12 3 2 4 5 1 7 8 11 10 9 6

输出:

说明:

良神下了1单，买了12件物品，免去了最低价格的物品费用（1块），加上12块运费，一共花费78-1+12=89块。

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3(3.5.2) 解法, 执行用时: 18ms, 内存消耗: 3392K, 提交时间: 2020-08-23 10:36:59

n = int(input())
a = [int(i) for i in input().split()]
if len(a) < 12:
    print(sum(a)+12)
elif len(a) == 12:
    print(sum(a)+12-min(a))
else:
    mix = sum(a)
    a.sort()
    f = 1
    while n>12:
        if a[n-12]>12:
            f+=1
            a[n-12]=0
        else:
            break
        n -=12
    mix=sum(a)+12*f-a[0]
    print(mix)

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 380K, 提交时间: 2020-11-01 13:07:35

#include<bits/stdc++.h>
using namespace std;int main()
{int n,sum=0;int a[1205];cin>>n;
for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}sort(a,a+n);
for(int i=n-12;i>0;i-=12){if(a[i]>12)sum=sum+12-a[i];}
sum=sum+12-a[0];cout<<sum;}