上海市计算机学会竞赛平台2025年1月月赛丙组音乐播放

题目描述

Bob 收藏了 nn 首有趣的音乐唱片，第 ii 首长 mimi​ 分钟，其语言为 lili​。

某天，Bob 想听语言为 LL 的歌，他希望选出恰好 kk 张唱片，这些唱片中的音乐都是语言为 LL 的，并且它们的总时长越长越好。

Bob 希望你帮忙找出他能听满足条件的音乐唱片的最大总时长，或者报告不能找到 kk 张这样的唱片。

输入格式

第一行一个整数 TT 表示数据组数。

对于每组数据：

第一行三个整数 n,k,Ln,k,L。

接下来 nn 行，每行两个整数 mi,limi​,li​ 表示第 ii 首歌的时长和语言。

输出格式

对于每组数据，如果能选出 kk 张符合要求的唱片，输出一行一个整数表示最大总时长，否则输出一行 -1。

数据范围

对于 30%30% 的数据，L=li=1L=li​=1，mi=1mi​=1。

对于 60%60% 的数据，L=li=1L=li​=1。

对于 100%100% 的数据，1≤T≤2001≤T≤200，1≤k≤n≤10001≤k≤n≤1000，1≤L≤51≤L≤5，1≤mi≤1001≤mi​≤100，1≤li≤51≤li​≤5。

样例数据

输入:

输出:

7
12
-1
8

说明:

对于第一组数据，有 1,3 两首语言为 2 的音乐，时长分别为 5,7，则选择时长为 7 的可以达到目标。

4
3 1 2
5 2
8 4
7 2
3 2 2
5 2
8 4
7 2
3 1 1
5 2
8 4
7 2
3 1 4
5 2
8 4
7 2

详见代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin >> t;
  while(t--) 
  {    
    int n, k, l;
    cin >> n >> k >> l;
    vector <int> a;
    for(int i = 1; i <= n; i++) 
    {
      int x, y;
      cin >> x >> y;
      if (y == l) 
      {
        a.push_back(x);
      }
    }
    if (a.size() < k) 
    { 
      cout << -1 << endl;
      continue;
    }
    sort(a.begin(), a.end(), greater<int>());
    int sum = 0; 
    for(int i = 0; i < k; i++) 
    {
      sum += a[i];
    }
    cout << sum << endl;
  }
  return 0;
}