题解 | #C. Kevin的抱团游戏#

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

C. Kevin的抱团游戏

很有意思的一道题

男生贡献1， 女生贡献2， 团为k大小，求落单的最少个数

思路分析

对于a，b两个变量，求最优组合解？

这题的指导思路是：反悔堆

至少我是这么去组织思路的。

• 优先安排女生，尽量让所有的女生组团
• 男生去填补女生留下的空，完成团
• 多余的男生去开拓新的团
• 剩下的男生2:1 去替换女生

为啥说这是反悔堆思路呢？

• 优先耗尽a，然后逐个增加b，记录此过程中的最大值。

这题的组团，是有点麻烦, 而且要考虑k的奇偶。

思路题：

假如这题男生贡献为x，女生贡献为y，那又如何解呢？

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        AReader sc = new AReader();
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
            // 怎么感觉像反悔堆形态
            // 分配完所有的女生组, 在置换男生组

            // 特判k==1
            if (k == 1) {
                System.out.println(m);
                continue;
            }

            int k2 = k / 2;  // 一个组最多能容纳女生的个数
            int g = m / k2;  // 按最大数，能构建几个组
            int left = m % k2; // 剩余的人数未成组

            int girlInGroup = g * k2;
            int ans = n + m;
            if (k % 2 == 1) {
                if (n <= g) {
                    System.out.println(m - k2 * n);
                    continue;
                }
                n -= g;
            } 
            
            ans = Math.min(ans, m - girlInGroup + n);

            // 余数的那个女生组，先填满
            if (n >= k - 2 * left) {
                n -= (k - 2 * left);
                girlInGroup += left;
                ans = Math.min(ans, (m - girlInGroup) + n);
            }
            // 男生组，构建新的组
            if (n >= k) {
                n %= k;
                ans = Math.min(ans, (m - girlInGroup) + n);
            }

            // 这边是反悔堆的核心，2个男生置换1个女生
            if (n >= 2) {
                int d = Math.min(n / 2, girlInGroup);
                n -= 2 * d;
                girlInGroup -= d;
                ans = Math.min(ans, (m - girlInGroup) + n);
            }
            System.out.println(ans);
        }
    }

    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }
        // 若需要nextDouble等方法，请自行调用Double.parseDouble包装
    }

}