Children play games (greedy, prefix sum) – Niu Ke winter training camp

Hits: 0

Original title link

topic

ideas

  1. First of all, to meet the requirements (every two noisy children need a quiet child), then there can only be at most n / 2 n/2 n/2noisy kid
  2. If there are not enough quiet children n / 2 + n   m o d   2 n/2+n\ mod\ 2 n/2+n mod 2, then output -1.
  3. For the rest, let the quiet children and the noisy children sort them in descending order of happiness.
  4. then find the prefix sum
  5. The last comparison is the least used n / 2 n/2 n/2What is the greatest happiness of being a quiet child.

code

//
// Created by saber on 2022/2/15.
//

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int suma[N] = {0};
int sumb[N] = {0};
bool cmp(int a, int b)
{
        return a > b;
}
int main()
{
    int t; cin >> t;
    while (t -- )
    {
        int a, b, n;
        cin >> a >> b >> n;
        memset(suma, 0, sizeof suma);
        memset(sumb, 0, sizeof sumb);
        for (int i = 1; i <= a; i ++ )
        {
            cin >> suma[i];
        }
        for (int i = 1; i <= b; i ++ )
        {
            cin >> sumb[i];
        }
        sort(sum + 1 , sum + 1 + a, cmp);
        sort(sumb + 1 , sumb + 1 + b, cmp);

        for (int i = 1; i <= a; i ++ )
        {
                sum[i] += sum[i - 1 ];
        }
        for (int i = 1; i <= b; i ++ )
        {
                sumb[i] += sumb[i - 1 ];
        }

        int maxn = 0;
        int f = n/2 + (n % 2);
        if (a < f)
        {
                cout << -1 << endl;
                continue;
                }

        for (int i = f; i <= min(a, n); i ++ )
        {
                maxn = max(suma[i] + sumb[n - i], maxn);
                }
                cout << maxn << endl;
    }

    return 0;
}

Summarize

I don’t understand why such a simple topic cannot be written during the competition.

You may also like...

Leave a Reply

Your email address will not be published.