记录70

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main(){
	long long n,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	int t=n;
	if(n%2) t++;
	t/=2;
	for(int i=n;i>n-t;i--){
		if(a[i]<=0) break;
		sum+=a[i];
	}
	cout<<sum;
	return 0;
}

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

突破口

他家只有一排 n 个座位，而且因为社交距离，两个人不能坐在相邻的座位上。

👉隔一个人坐一个，例6个人要3个座位，7个人要4个座位

这些朋友的快乐值的和最大为多少

👉 贪心问题

思路

1. 从小到大排序，找到阳光开朗大男孩
2. 确认座位
3. 进行累加

代码简析

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main(){
	long long n,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	int t=n;
	if(n%2) t++;
	t/=2;
	for(int i=n;i>n-t;i--){
		if(a[i]<=0) break;
		sum+=a[i];
	}
	cout<<sum;
	return 0;
}

long long n（ n 个朋友）,sum=0（最大快乐值）; 👉 累加就想到long long，防止加爆

sort(a+1,a+n+1); 👉 按照开朗值排名

int t=n（座位）; 👉 准备处理座位

if(n%2) t++;  👉  偶数变奇数

t/=2; 👉得到能做几个人

for(int i=n;i>n-t;i--){...} 👉 从后向前找，不包括n-t号人

例：编号1到9 ，倒着找后三人，找到的是9，8，7 不包括9-3(6)号

if(a[i]<=0) break; 👉 遇到不想来的，强扭的瓜不甜，不邀请

sum+=a[i]; 👉 把想来的人进行统计快乐值

补充

以下是 CSP-J 中常见的贪心算法问题知识点类型，按问题特征和策略分类汇总，不涉及具体题目编号，仅说明题型本质：

---

1. 区间调度类

• 特点：给定若干区间（如任务的开始/结束时间），要求选出最多（或满足条件）的不重叠区间。
• 贪心策略：按结束时间升序排序，优先选择最早结束的区间。

---

2. 活动安排 / 任务选择类

• 变种：教室安排、会议安排、节目选择等。
• 核心思想：局部最优（尽早释放资源） → 全局最优。

---

3. 分配/装载类

• 特点：将物品分配给若干容器（如货车装货、分糖果、分组），在限制条件下最大化数量或满足公平性。
• 常见策略：
  • 按重量/体积从小到大装（最大化数量）
  • 或按价值密度排序（但 CSP-J 一般不涉及分数背包）

注：CSP-J 通常只考整数、不可分割的物品，即0-1 背包不会用贪心，但若题目有特殊结构（如“每个物品代价相同”），则可贪心。

---

4. 排队/顺序优化类

• 特点：安排人员或任务的处理顺序，使总等待时间、平均耗时等最小。
• 经典策略：
  • 按处理时间升序排列（最短任务优先）
  • 如：排队打水、打印任务调度

---

5. 找零/货币支付类

• 特点：用最少张数（或特定规则）凑出某个金额。
• 贪心前提：币值系统为规范币制（如人民币：1, 5, 10, 20, 50, 100）
• 策略：从大面额到小面额依次取。

⚠️ 注意：并非所有币值系统都适用贪心（但 CSP-J 题目默认可贪心）。

---

6. 合并/切割代价最小化类

• 特点：多次合并或切割，每次操作有代价，求总代价最小。
• 常见误区：
  • 合并果子类（哈夫曼编码）→ 实际需用优先队列，严格来说是贪心+堆，CSP-J 偶尔出现简化版（如固定顺序合并）。
  • 若题目允许任意顺序合并且代价为两堆之和，则属于贪心（但需堆优化）。

在 CSP-J 中，若数据规模小（如 n ≤ 1000），可能直接模拟；若强调“每次合并最小的两个”，则归为贪心思想。

---

7. 字典序最小/最大构造类

• 特点：构造一个序列、字符串或路径，使其字典序最小（或最大）。
• 贪心策略：每一步在合法前提下，选择当前最小（或最大）的可用元素。

---

8. 覆盖/选取点类

• 例子：在数轴上放置最少的点，使得每个给定区间内至少包含一个点。
• 策略：按区间右端点排序，在右端点处放点（经典“区间覆盖”模型）。

---

9. 局部最优即全局最优的模拟类

• 特点：问题看似复杂，但每一步做“当前看起来最好”的选择，最终结果最优。
• 典型场景：
  • 跳跃游戏（每次跳最远）
  • 分段累加（如“尽可能早地切断以满足条件”）
  • 游戏得分最大化（每轮选最高分选项）

---

10. 双指针 + 贪心结合类

• 特点：在有序数组中，通过左右指针移动，贪心地逼近目标（如配对、求和）。
• 策略：根据当前和与目标的关系，决定移动左/右指针。

---

总结：CSP-J 贪心问题的核心特征

• 无后效性：当前决策不影响未来选择的可行性。
• 局部最优 = 全局最优：可通过数学证明或直觉验证。
• 排序是关键：绝大多数贪心题需先对输入数据排序（按时间、大小、性价比等）。
• 不涉及动态规划状态转移：若需要“回头考虑之前的选择”，则不是贪心。

掌握以上类型，即可覆盖 CSP-J 中 90% 以上的贪心考点。