NowCoder 203D – Shopping (贪心)

Table of Contents

题意

你有$n$个商品要买,总共有$m$个购物车。如果购物车内买了个凳子,那么这个购物车最贵的商品半价。问你最小的花费是多少。

思路

最多只能有$m$或者凳子数量个商品半价。半价商品一定是最贵的。

代码

#include <bits/stdc++.h>
using namespace std;
 
int n = 0, m = 0;
int s[1005] = {};
double total = 0;
 
int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    total = 0;
    scanf("%d%d", &n, &m);
 
    int tmp = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
      scanf("%d%d", s + i, &tmp);
      if (tmp == 1) cnt++;
    }
 
    m = min(m, cnt);
    sort(s, s+n);
 
    for (int i = 1; i <= m; ++i) {
      total += (double) s[n - i] / 2;
    }
    for (int i = 0; i < n - m; ++i) {
      total += s[i];
    }
 
    printf("%.1lf\n", total);
 
  }
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注