原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=5999
The Third Cup is free
Panda and his friends were hiking in the forest. They came across a coffee bar inside a giant tree trunk.
Panda decided to treat everyone a cup of coffee and have some rest. Mr. Buck, the bartender greeted Panda and his animal friends with his antler. He proudly told them that his coffee is the best in the forest and this bar is a Michelin-starred bar, thats why the bar is called Starred Bucks.
There was a campaign running at the coffee bar: for every 3 cups of coffee, the cheapest one is FREE. After asking all his friends for their flavors, Panda wondered how much he need to pay.
Input
The first line of the input gives the number of test cases, T.
T test cases follow. Each test case consists of two lines. The first line contains one integer N, the number of cups to be bought.
The second line contains N integers p1,p2,⋅⋅⋅,pNp1,p2,···,pN representing the prices of each cup of coffee.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the least amount of money Panda need to pay.
limits
- 1 ≤ T ≤ 100.
- 1 ≤ N ≤ 105105.
- 1 ≤ pi ≤ 1000.
Sample
Input
2
3
1 2 3
5
10 20 30 20 20
Output
Case #1: 5
Case #2: 80
容易踩的坑
用从小到大排序后，减去杯数/3杯最便宜的咖啡的方法。
这种方法很显然，减去的是一堆便宜咖啡中最便宜的咖啡，不是最少花费
思路
那么接下来就很清晰了，连续读入每杯咖啡的价格，然后进行从大到小排序，加入一个cnt计数当前第几杯，每当读取到第三杯时，则不把当前咖啡计入总价格内。
具体解法
- 排序优化：利用数组下标为价格的方式来存储每个价格咖啡的杯数，从而省去一个排序的耗时。如n[20]为价格为20元的咖啡的杯数。
- 然后开搞
#include<stdio.h>
int n[1050];//咖啡价格区间
int main(void) {
int T, k = 1, a;
scanf("%d", &T);
while (T--)
{
long long ans = 0, cnt = 0, cups;
scanf("%lld", &cups);
for (int i = 0; i < cups; i++)//开始读取
{
scanf("%d", &a);
n[a]++;
}
for (int i = 1000; i > 0; i--)
{
while (n[i])
{
cnt++;
if (!(cnt % 3))
cnt = 0;
else ans += i;
n[i]--;
}
}
printf("Case #%d: %lld\n", k++, ans);
}
return 0;
}TLE
Accept
杂谈
这种排序法，在不要求输入次序的时候蛮好用的。
主要纪念一下第一次荣登VJ排行榜，留个小纪念。
京公网安备 11010502036488号