专题 | 贪心
贪心¶
贪心算法的基本思路¶
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
贪心算法适用的问题¶
贪心策略的前提是：局部最优策略能导致产生全局最优解。
例题 #1 排队接水¶
题目描述
有 \(n\) 个人在一个水龙头前排队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 \(n\) 个人排队的一种顺序，使得 \(n\) 个人的平均等待时间最小。
输入格式
第一行为一个整数 \(n\)。
第二行 \(n\) 个整数，第 \(i\) 个整数 \(T_i\) 表示第 \(i\) 个人的等待时间 \(T_i\)。
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
提示
\(n \leq 1000,t_i \leq 10^6\)，不保证 \(t_i\) 不重复。
当 \(t_i\) 重复时，按照输入顺序即可（sort 是可以的）
/*////////ACACACACACACAC///////////
Code By Ntsc
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5;
int idx,ans;
struct node{
int num,id;
}h[N];
bool cmp(node a,node b){
return a.num<b.num;
}
signed main(){
int n,idx=0;
cin>>n;
for(int i=1;i<=n;i++){
int tmp;
cin>>tmp;
idx++;
h[idx]={tmp,idx};
}
sort(h+1,h+n+1,cmp);
for(int i=1;i<=n;i++)cout<<h[i].id<<' ';
for(int i=1;i<n;i++){
ans+=h[i].num*(n-i);
}
printf("\n%.2lf",1.00*ans/n);
return 0;
}
例题 #2 [NOIP2004 提高组] 合并果子¶
题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 \(n-1\) 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 \(1\) ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有 \(3\) 种果子，数目依次为 \(1\) ， \(2\) ， \(9\) 。可以先将 \(1\) 、 \(2\) 堆合并，新堆数目为 \(3\) ，耗费体力为 \(3\) 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 \(12\) ，耗费体力为 \(12\) 。所以多多总共耗费体力 \(=3+12=15\) 。可以证明 \(15\) 为最小的体力耗费值。
输入格式
共两行。 第一行是一个整数 \(n(1\leq n\leq 10000)\) ，表示果子的种类数。
第二行包含 \(n\) 个整数，用空格分隔，第 \(i\) 个整数 \(a_i(1\leq a_i\leq 20000)\) 是第 \(i\) 种果子的数目。
输出格式
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 \(2^{31}\) 。
提示
对于全部的数据，保证有 \(n \le 10000\)。
堆¶
-
Heap是一种数据结构具有以下的特点： 1）完全二叉树； 2）heap中存储的值是**偏序**；
-
Min-heap 小**根堆: 任意父节点的值小于或等于子节点的值；即对于任何子树，其根≤其中任何节点 **Max-heap 大根堆: 任意父节点的值大于或等于子节点的值；
Priority_queue¶
定义方式
priority_queue<int> pq;//默认构建的是一个大根堆，所以每次从头取数据得到的是一个从大到小的队列排序.
//or
priority_queue<int, vector<int>, less<int> >
小根堆定义方式
priority_queue<int, vector<int>, greater<int> >//greater代表越大的越深
每次取出所有堆中数量最少的2堆，合并后放回其它堆中
实现方法：priority_queue
#include<bits/stdc++.h>
using namespace std;
int n,a,ans;
priority_queue<int> pq;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;pq.push(-a);
}
while(pq.size()){
int a,b;
a=-pq.top();pq.pop();
if(pq.size()){
b=-pq.top();pq.pop();
ans+=a+b;
pq.push(-a-b);
}
}
cout<<ans;
return 0;
}
例题 #3 田忌赛马 [ZJOI2008] 泡泡堂¶
第 XXXX 届 NOI 期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由 \(n\) 名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，\(n\) 号选手捉对厮杀，共进行 \(n\) 场比赛。每胜一场比赛得 \(2\) 分，平一场得 \(1\) 分，输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。
作为浙江队的领队，你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚，并将其用一个实力值来衡量。为简化问题，我们假定选手在游戏中完全不受任何外界因素干扰，即实力强的选手一定可以战胜实力弱的选手，而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序，所以所有的队伍都采取了这样一种策略，就是完全随机决定出场顺序。
当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下，浙江队最终分别能得到多少分。
输入格式
输入文件的第一行为一个整数 \(n\)，表示每支代表队的人数。
接下来 \(n\) 行，每行一个整数，描述了 \(n\) 位浙江队的选手的实力值。
接下来 \(n\) 行，每行一个整数，描述了你的对手的 \(n\) 位选手的实力值。
输出格式
输入文件中包括两个用空格隔开的整数，分别表示浙江队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。
\(100\%\) 的数据中，\(1\leq n\leq 100000\)，且所有选手的实力值在 \(0\) 到 \(10000000\) 之间。
n项田忌赛马策略（最优）：
比较两者最佳选手，能赢就赢。
否则比较最弱选手，能赢就赢
否则就使用最弱选手对对方的最强选手。注意这里要判断平局。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int a[N];
int b[N];
void solve(){
int n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
for(int j=1;j<=n;j++){
b[j]=rd;
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int ans=0;
{
int al=1,ar=n;
int bl=1,br=n;
for(int i=1;i<=n;i++){
if(a[ar]>b[br]){
ar--;
br--;
ans+=2;
}else if(a[al]>b[bl]){
al++;
bl++;
ans+=2;
}else{
if(a[al]==b[br])ans++;
al++;
br--;
}
}
cout<<ans<< ' ';
}
ans=0;
swap(a,b);
{
int al=1,ar=n;
int bl=1,br=n;
for(int i=1;i<=n;i++){
if(a[ar]>b[br]){
ar--;
br--;
}else if(a[al]>b[bl]){
al++;
bl++;
}else{
if(a[al]==b[br])ans++;
else ans+=2;
al++;
br--;
}
}
cout<<ans<<endl;
}
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
反悔贪心¶
见反悔贪心 反悔贪心
练习¶
带高精度乘除 难度 普及+/提高
更多：