记录122

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;// 定义常量 MAXN，根据题目 n, m <= 10^5
vector<int> ques[MAXN];// 静态数组配合动态数组：ques[i] 存储第 i 种算法的所有题目加分值
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m,n,k;// m为算法种类数，n为题目总数，k为目标掌握程度
	cin>>m>>n>>k;
	vector<int> a(n+1);// 数组 a 用于存储每道题对应的知识点编号（从下标 1 开始使用）
	vector<int> b(n+1);// 数组 b 用于存储每道题对应的加分值（从下标 1 开始使用）
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) ques[a[i]].push_back(b[i]);
	// 核心分组步骤：将第 i 道题的加分 b[i]，存入它所属的知识点 a[i] 对应的向量中
	long long total_ques=0; // 记录完成目标总共需要的最少题目数量（用 long long 防止累加溢出）
	int max_cnt=0; // 记录所有算法中，需求量最大的那个算法所需的题目数
	int mx_need_i=-1;// 【新增】用来记录需求量最大的那个知识点的编号
	for(int i=1;i<=m;i++){// 遍历 m 种算法，进行贪心处理
		sort(ques[i].begin(),ques[i].end(),greater<int>());
		// 将该算法对应的所有题目按加分从大到小排序，保证优先做加分高的题
		int cur_sum=0;// 当前算法的累计掌握程度
		int need_cnt=0;// 当前算法达到目标 k 所需要的题目数量
		for(int score:ques[i]){// 依次遍历排好序的题目加分
			cur_sum+=score;// 累加掌握程度
			need_cnt++; // 做题数量加一
			if(cur_sum>=k) break;// 一旦达到目标 k，立刻停止选择该算法的后续题目
		}
		if(cur_sum<k){// 如果该算法所有题目加起来都达不到目标 k，说明无解
			cout<<-1<<"\n";
			return 0;
		}
		total_ques+=need_cnt;// 将该算法所需的最少题目数加入总题数
		if(need_cnt>max_cnt){max_cnt=need_cnt;mx_need_i=i;}// 【修改】更新最大值的同时记录下标
	} 
	long long other_cnt=total_ques-max_cnt; // 计算除了需求最多的算法外，其余算法所需的总题数
	if(max_cnt<=other_cnt+1){// 【修改】如果普通插空能成功，直接输出并结束
		cout<<total_ques<<"\n";
		return 0;
	}
	// --- 【新增的补救逻辑】---
	// 走到这里说明普通插空失败，尝试去“借”其他知识点没用过的废题来当隔板
	long long last=0;// 记录其他知识点剩下的、没被选中的题目总数（工具人库存）
	for(int i=1;i<=m;i++){
		if(i!=mx_need_i){// 只统计除了最大需求者之外的其他知识点
			int used=0,sum=0;// 重新算一下第 i 个知识点实际用了多少道题
			for(int score:ques[i]){sum+=score;used++;if(sum>=k)break;}
			last+=ques[i].size()-used;// 总题数减去必须做的题数 = 可以借的废题数
		}
	}
	// 最终带工具人的插空判定：左边是必选题需要的空隙，右边是原本的其他题加上借来的废题
	if(max_cnt-1<=other_cnt+last)cout<<2LL*max_cnt-1<<"\n";// 能隔开！最优策略是排成 必选-工具人-必选... 的形式
	else cout<<-1<<"\n";// 就算借了所有废题也填不满空隙，彻底无解
	return 0;//结束程序 
}

---

题目传送门https://www.luogu.com.cn/problem/P11247

---

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

---

💡 核心解题思路推导

这道题可以拆解为三个步骤来解决：

第一步：贪心选取（最少做题数）

对于每一种算法知识点 ii ，我们的目标是用最少的题目数量让掌握度达到 kk 。

• 策略：将属于该知识点的所有题目按加分 bibi​ 从大到小排序。
• 操作：依次选取加分最高的题目，直到累计分数 ≥k≥k 。
• 记录：记录下每种知识点所需的最少题目数 need_cnt，以及所有知识点的总题目数 total_ques。

第二步：可行性初判（无解情况）

在贪心选取的过程中，如果发现某一种算法知识点，即使把所有相关题目都做了，分数 still <k<k ，那么直接输出 -1，因为目标无法达成。

第三步：插空排列（避免连续）

这是本题最难的逻辑点。假设我们已经算出了每种知识点需要做的题目数（cnt[1], cnt[2], ..., cnt[m]）。

• 找出最大值：设需求最大的知识点需要做 max_cnt 道题。
• 其余总和：设其他所有知识点需要做的题目总数为 other_cnt。
• 插空原理：要把 max_cnt 个相同的题目隔开（不能相邻），至少需要 max_cnt - 1 个其他知识点的题目来充当“隔板”。
  1. 情况 A（容易）：如果 other_cnt >= max_cnt - 1。
     • 说明我们手头的“其他必做题”足够多，可以直接插空。
     • 答案就是总题数 total_ques。
  2. 情况 B（困难）：如果 other_cnt < max_cnt - 1。
     • 说明“必做题”不够当隔板。这时我们需要去“借”那些不需要做的题目（即废题）来当工具人。
     • 计算废题数 last：遍历除最大需求知识点外的所有组，计算每组没被选中的题目数量（总题数 - 必做题数）。
     • 借题插空：如果 other_cnt + last >= max_cnt - 1，说明借了废题后能隔开。此时的最优排列策略是：[必选] [工具人/废题] [必选] ...。这种排列的最短长度是 2×max_cnt−12×max_cnt−1 。
     • 彻底无解：如果连废题都借光了还不够隔板，输出 -1。

---

🧩 代码解释

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10; // 定义数组大小常量，题目数据范围是 10^5
vector<int> ques[MAXN]; // 邻接表思想：ques[i] 存储所有属于知识点 i 的题目加分值

• 解释：这里使用了静态数组 ques 配合 vector，这是处理“分组数据”的常用高效写法。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); // 优化输入输出流，加快读取速度（题目数据量较大）
    
    int m,n,k;
    cin>>m>>n>>k;
    vector<int> a(n+1); // a[i] 表示第 i 道题的知识点编号
    vector<int> b(n+1); // b[i] 表示第 i 道题的加分值
    
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    
    // 核心分组逻辑
    for(int i=1;i<=n;i++) 
        ques[a[i]].push_back(b[i]);

• 解释：将输入的题目按知识点分类。例如所有知识点为 1 的题，其加分值都被放入 ques[1] 这个 vector 中。

    long long total_ques=0; // 总共需要做的题目数量（用 long long 防止累加溢出）
    int max_cnt=0;          // 记录单个知识点所需的最大题目数
    int mx_need_i=-1;       // 记录需求最大的那个知识点的编号（为了后面排除它计算废题）

• 解释：total_ques 定义为 long long 是为了保险，虽然题目 n≤10^5 ，但养成好习惯。

    // 遍历每一种算法知识点
    for(int i=1;i<=m;i++){
        // 1. 贪心排序：将该知识点下的题目按加分从大到小排序
        sort(ques[i].begin(),ques[i].end(),greater<int>());
        
        int cur_sum=0;     // 当前知识点累计分数
        int need_cnt=0;    // 当前知识点需要做的题目数
        
        // 2. 贪心选取：从高分题开始做，直到达到目标 k
        for(int score: ques[i]){
            cur_sum += score;
            need_cnt++;
            if(cur_sum >= k) break;
        }
        
        // 3. 判定无解：如果该知识点分数不够 k
        if(cur_sum < k){
            cout << -1 << "\n";
            return 0; // 直接结束程序
        }
        
        // 4. 更新全局变量
        total_ques += need_cnt;
        if(need_cnt > max_cnt){ 
            max_cnt = need_cnt; 
            mx_need_i = i; // 记录下是哪个知识点需求最大
        }
    } 

• 解释：这是第一阶段的逻辑，确定了“最少要做哪些题”。

    long long other_cnt = total_ques - max_cnt; // 其他知识点需要做的题目总数
    
    // 情况 A：如果其他题足够作为隔板 (other_cnt >= max_cnt - 1)
    if(max_cnt <= other_cnt + 1){
        cout << total_ques << "\n";
        return 0;
    }

• 解释：max_cnt <= other_cnt + 1 等价于 max_cnt - 1 <= other_cnt。这是插空法的基本公式。

    // 情况 B：其他“必做题”不够当隔板，需要借“废题”
    long long last = 0; // 统计可以借来的“废题”数量
    
    for(int i=1;i<=m;i++){
        if(i != mx_need_i){ // 只统计非最大需求的知识点（不能借自己的废题）
            int used = 0, sum = 0;
            // 重新计算该知识点实际用了多少道“必做题”
            for(int score: ques[i]){ 
                sum += score; 
                used++; 
                if(sum >= k) break;
            }
            // 累加该知识点的“废题”数量（总题数 - 必做题数）
            last += ques[i].size() - used; 
        }
    }
    
    // 最终判定：借了废题后，隔板是否够用？
    // max_cnt - 1 是需要的隔板数
    // other_cnt + last 是现有的隔板总数（必做题 + 废题）
    if(max_cnt - 1 <= other_cnt + last)
        cout << 2LL * max_cnt - 1 << "\n"; // 能隔开！最短长度是 2*max_cnt - 1
    else 
        cout << -1 << "\n"; // 彻底无解

• 解释：2LL * max_cnt - 1 中的 LL 表示 Long Long，防止乘法溢出。这个公式的含义是：max_cnt 个必选题，中间插入 max_cnt - 1 个工具人（废题），总长度即为 n+(n−1)=2n−1n+(n−1)=2n−1 。

---

算法思维提炼

维度	经验总结	避坑指南
题眼识别	看到“最少做题数” →→ 贪心；看到“不能连续相同” →→ 插空法	不要盲目套用模板，需根据题意组合使用
极值思维	排列约束问题中，需求量最大的元素决定了整体结构	必须记录最大值及其下标，它是后续所有判定的基准
隐藏资源	题目中“未被选中的冗余数据”往往是破局的关键工具	当常规条件不满足时，检查是否有“废料”可以二次利用
数据类型	涉及大量累加和乘法运算时，需防范整数溢出	使用 long long 并在乘法时加上 LL 后缀