2016CCPC Finals[HDU-5999]The Third Cup is Free题解

原题链接：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;
}