题解 | #良神爱购物#

题号：NC14401

链接：https://ac.nowcoder.com/acm/problem/14401

来源：牛客网

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

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

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

输入

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

输出

89

在说思路之前，先吐槽下：

在我测试的时候，oj的测试数据是有错误测试数据的，而错误数据的原因我也知道，因此可以写本文题解。

错误的数据：当剩余订单不足12件的时候，是不能免去最小件的价格，但是错误数据却免去了。

思路：

这是明显贪心算法的题目。

题解的乘号打不出来，用X替代

想要更低价格，是凑多个订单，省每个订单的最低价格，同时需要额外的12元运费。如果这些商品的价格不足或者等于12元，显然这种做法不合适（运费这么贵）。因此这些小于等于12元的商品不能分多个订单买。

分多个订单买的，只能是商品价格大于12元的，这些都需要尽量分多个订单买。比如12 X k个商品的价格大于12元，分k个订单买，按照商品的价格升序（从1开始），省掉的将是第1+12 X 0,1+12 X 1,1+12 X 2,....个商品的价格。如果有12 X k+m个商品价格大于12元，12 X k分k个订单，剩下的m个和小于等于12元的商品是没有活动优惠，只能有两种策略，单独作为一个订单，或者加入到一个已有的订单（前面所说商品1-12的订单）。

策略A:加入已有的订单，省掉12元运费，但是加入那个订单的原先订单的最低价格变为没有优惠（大于12元),而且剩下m个和小于等于12元的那些商品的最低价格却是有优惠。

如果作为单独的订单，也是分为两种：

策略B1:数量达到12个以及以上，需要12元运费，同时剩下m个和小于等于12元的那些商品的最低价格是有优惠,明显比策略A好。

策略B2:数量未达到12个，仅仅需要12元运费。可能比策略A好，可能比策略A差.而测试数据就是在算这个出现异常，未达到12个，也把最低那个商品价格给优惠了。（77%通过了，基本证明你的写法是对的）

附代码：

// dddd.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
// dddd.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int main() {
	int n,x;
	int data2[2000];
	int top = 0;
	int total = 0;
	cin>>n;
	int minV = 0;
	for (int i = 0; i < n; i++) {
		cin >> x;
		//小于等于12元的直接付款，不参与活动
		if(x>12) data2[top++] = x;
		// 记录全部的最小件数
		if (i == 0|| x < minV) minV = x;
		// 统计所有的件数价格
		total += x;
	}
	// 使用贪心算法,先选出最高11个，下一个最高的进行参与活动（参与活动的该件价格变为12）
	// 先进行冒泡排序
	for (int i = 0; i < top - 1; i++) {
		for (int j = 0; j < top - 1 - i; j++) {
			if (data2[j] > data2[j + 1]) {
				data2[j] ^= data2[j + 1];
				data2[j+1] ^= data2[j];
				data2[j] ^= data2[j + 1];
			}
		}
	}
	int select = top-12;
	while (select >= 0) {
		total += 12-data2[select];
		select -= 12;
	}

	if (top >= 12) {
		//所有购买小于等于12的，和无法参与活动的剩余件数有两种策略：
		//1.都拼在最后1单上
		int total1 = total + data2[select + 12] - minV;
		//2.另外再起一单，如果再起一单的数量大于等于12，去掉最小件
		// 正确应该是这个：int total2 = total + 12 + (n-top+(select + 12)>=12?-minV:0);
		int total2 = total + 12 + (n-top+(select + 12)>=12?-minV:-minV);
		total = total1 < total2 ? total1 : total2;
		cout << total << endl;
	}
	else {
		//无法贪心参与活动，并且还有支付运费,但是因为n是必然大于等于12，可以省最小一件
		cout << (total - minV+12) << endl;
	}
	//25
	//2 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13
}

附测试数据： 13 5 13 13 13 13 13 13 13 13 13 13 13 13

168?还是167？