信奥一本通 贪心算法 回顾

文章目录

• 写在前面
• • • A 家庭作业
    • B 智力大冲浪
    • C 加工生产调度
    • D 喷水装置3(线段覆盖最少线段)
    • E. 活动安排(线段覆盖，覆盖最多段)
    • F 种树
    • G 数列极差
    • H 数列分段
    • I 钓鱼
    • J 均分纸牌
    • K 糖果传递

写在前面

之前看到一篇非常好的博客 ， 上面的一句话让我记忆很深 ，“事实上现在也有很多人认为贪心题必须要排序，但排序和贪心从来没有任何关系。重要的是，贪心只是一种思想，而排序只是为了降低时间复杂度。排序恰好契合了贪心一直选当前最优的思想，能够将每次重新找最优变为连续的从优到劣。堆经常被用来做贪心题亦是如此。如果一直想着“我应该按哪一维排序”或者“堆的排序关键字是什么”这种问题，而不想贪心究竟是为了什么，那就得不偿失了。”

A 家庭作业

家庭作业

思路：满足贪心的无后效性 ， 我们考虑用贪心做
但是如何贪心呢 ， 如果我们按照第一维时间排序
那么我们可以找出一组反例是

4
1 3
2 10
2 10
3 1

这样贪心选选到的是

1 3
2 10
3 1

但显然最优答案是

2 10
2 10
3 1

如果我们按照第二维价格贪心
那么也能找出一组反例是

4
1 9
2 8
2 10
3 7

这样选到的就是

2 10
2 8
3 7

但是最优解是

1 9
2 10
3 7

这时候我们就需要思考一下我们确实应该先按时间排序 ，保证先处理时间小的 ， 但是如果在后面时间大的里面出现了比前面方案更优的存在时，我们应该把前面的去掉

例如

4
1 3
2 10
2 10
3 1

先选 1 3
再选 2 10
然后选 2 10
这时候我们发现选的个数超过了期限时间，而且2 10 明显 优于 1 3 ， 我们就把 1 3 卡掉，用 2 10 代替 1 3 ，当然了如果第三个是 2 2，我们肯定就不会替换 ， 用小根堆模拟这个过程
最后选 3 1

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;struct node{int x,y;
}a[N];bool cmp(node a,node b){return a.x<b.x||(a.x==b.x&&a.y>b.y);
}//按时间排序int n;
priority_queue<int,vector<int>,greater<int>> q;//小根堆int main(){IOS;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}	sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){q.push(a[i].y);while(q.size()>a[i].x) q.pop();}//q.size() 是当前要消耗的时间 ， a[i].x 是期限 ，当消耗时间大于期限的时候我们考虑替换int ans = 0;while(!q.empty()){ans += q.top();q.pop();}cout<<ans;
}

B 智力大冲浪

智力大冲浪

思路与 A题相同，把选中的标记一下即可；

C 加工生产调度

思路：
满足贪心的无后效性 ， 我们考虑如何贪心
我们找一下两组之间的关系去推整体的关系

假设

a1 a2
b1 b2

这个排序满足时间最小
那一定有

$a1+max(a2,b1)+b2>=a2+max(a1,b2)+b1$

移项

$max(a2,b1)-a2-b1>=max(a1,b2)-a1-b2$

化简
$-min(a2,b1)>=-min(a1,b2)$
$min(a2,b1)<=min(a1,b2)$

但是这个式子不满足严格弱序

给出大佬的文章

浅谈邻项交换排序的应用以及需要注意的问题

记下结论了

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e4+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;int n,min1 = 1e9+10,min2 = 1e9+10;
int sum1 , sum2 , ans;struct node{ int a,b,id;
}a[N];bool cmp(node x,node y){return min(x.a , y.b) < min(y.a ,x.b) || (min(x.a , y.b) == min(y.a , x.b) && x.a < y.a);
}int main(){IOS;cin >> n;for(int i=1;i<=n;i++){cin >> a[i].a; }for(int i=1;i<=n;i++){cin >> a[i].b; a[i].id = i;}sort(a+1,a+1+n,cmp);int t1 = a[1].a , t2 = a[1].a + a[1].b;for(int i=2;i<=n;i++){t2 = max( t1 + a[i].a , t2 ) + a[i].b;t1 += a[i].a;}cout << t2 << "\n";for(int i=1;i<=n;i++){cout << a[i].id << " ";}
}

D 喷水装置3(线段覆盖最少线段)

喷水装置3

每个喷头真正覆盖的位置是与草坪的交点 ， 知道了 喷头横坐标和半径后，我们就能算出每个喷头覆盖的真正范围，就变成了一个线段覆盖问题 ， 用最少的线段 ， 考虑贪心 ， 贪心思路是在合法的范围内选择右边界最远的地方，不断更新右边界直到覆盖完成 ，注意无法覆盖断开的情况

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;int t,n;
double len,w;struct node{double l,r;
}a[N];bool cmp(node a,node b){return a.l<b.l||(a.l==b.l&&a.r<b.r);
}int main(){cin >> t;while(t--){cin >> n >> len >> w ;double x,r;int cnt=0;for(int i = 1 ;i <= n ; i++){cin>>x>>r;if(2*r>w){a[++cnt].l = x - sqrt(r*r-(w/2)*(w/2));a[cnt].r   = x + sqrt(r*r-(w/2)*(w/2));
//				cout<}}sort(a+1,a+1+cnt,cmp);a[++cnt].l = 1e9 + 10;a[cnt].r   = 1e9 + 10;//存下所有线段长度然后排序//		for(int i=1;i<=cnt;i++){
//			cout<
//		}double now = 0,max1 = 0;int ans = 0,f = 1;for(int i=1;i<=cnt;   ){if(a[i].l <= now){max1=max(max1,a[i].r);i++;}else{if(now == max1){f = 0;break;}now = max1;max1 = 0;ans++; 
//				cout<< now << " " << ans << " " << i <<"\n";if(now >= len){break;}}}if( !f ) printf("-1\n");else printf("%d\n",ans);}return 0;
}

E. 活动安排(线段覆盖，覆盖最多段)

活动安排
贪心思路：
放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少
其他线段放置按右端点排序，贪心放置线段，即能放就放

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;int n;struct node{int l,r;
}a[N];bool cmp(node a,node b){return a.r<b.r;
}//越早结束越好int main(){IOS;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].l>>a[i].r;}sort(a+1,a+1+n,cmp);int now = 0,ans = 0;for(int i=1;i<=n;i++){if(a[i].l >= now){now = a[i].r;ans++;}}cout<< ans ;return 0;
}

F 种树

种树

思路：为了尽可能的少种树 ， 我们考虑尽可能把树种在重叠部分 ， 树会在两个线段的尾部重叠 ， 我们按照线段右边界进行排序 ，从线段右端开始种树，让重叠部分尽可能最大

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e4+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;int n,h;
// 两个区间可能会在前一个区间的尾部重叠，考虑每次先放尾部的尽可能多的放重叠部分struct node{int l,r,res;
}a[N];bool cmp(node a,node b){return a.r< b.r;
}int vis[NN],ans;int main(){cin>>n>>h;for(int i=1;i<=h;i++){cin>>a[i].l>>a[i].r>>a[i].res;}sort(a+1,a+1+h,cmp);for(int i=1;i<=h;i++){int res=0;for(int j=a[i].l;j<=a[i].r;j++){if(vis[j]) res++;}//		cout<< a[i].res<<"\n";if(res >= a[i].res) continue;else a[i].res -= res;for(int j=a[i].r;j>=a[i].l && a[i].res;j--){ if(!vis[j]){
//				cout<< j <<"\n";vis[j] = 1;a[i].res--;ans++;}}}cout<< ans ;return 0;
}

G 数列极差

数列极差

思路：我们模拟这个过程发现 ， 要想这个操作尽可能大 ，大数应该在后面操作 ， 尽可能小的话 ， 小的数尽可能在后面操作

用大根堆和小根堆模拟操作即可

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;int n,m;
int a[N];
priority_queue<int,vector<int>,less<int>   > pmax;
priority_queue<int,vector<int>,greater<int>> pmin;
int maxx1(){while(pmin.size() > 1){int a = pmin.top();pmin.pop();int b = pmin.top();pmin.pop();pmin.push(a*b+1);}return (int)pmin.top();
}int minn1(){while(pmax.size() > 1){int a = pmax.top();pmax.pop();int b = pmax.top();pmax.pop();pmax.push(a*b+1);}return (int)pmax.top();
}int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);pmax.push(a[i]);pmin.push(a[i]);}cin>>n;int ans = maxx1() - minn1(); cout<< ans;}

H 数列分段

数列分段
思路：贪心 ， 每次尽量使所有段总和接近最大值

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;int n,m;
int a[N];int main(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[n+1] = 1e9+10;int now = 0 , ans = 0;for(int i=1;i<=n+1;i++){if(now + a[i] <= m){now += a[i];}else{ans++;now = a[i];}}cout<< ans;
}

I 钓鱼

我们要求最多钓到的鱼的数量 ， 我们可以贪心求解 ，但是现在最大的问题就是如何计算路径上的消耗 ， 我们不知道最远要走到那里也就无法进行贪心，这时候我们发现数据范围很小 ，我们可以暴力枚举最远的池塘然后进行贪心

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e3+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;int h,n,ans,max1;
int a[101];
int w[101];
int s[101];
priority_queue<PII,vector<PII>,less<PII>> q;
int main(){cin >> n >> h;h = h * 12;for(int i=1;i<=n;i++){cin >> a[i];}for(int i=1;i<=n;i++){cin >> w[i];}for(int i=1;i<n;i++){cin >> s[i];s[i] += s[i-1];}// 暴力枚举终点for(int i=1;i<=n;i++){int now = h;int ans = 0;now -= s[i-1];//		cout << now << "\n";while(!q.empty()) q.pop();for(int j=1;j<=i;j++){q.push({a[j] , j});}while( now > 0 && !q.empty() ){PII t = q.top();q.pop();now--;if(t.fi == 0) break;ans += t.fi;t.fi = max(0 , t.fi - w[t.se]);if(t.fi != 0) q.push(t);}max1 = max(max1 , ans);}cout<< max1;return 0;
}

J 均分纸牌

均分纸牌

我们假设 Ai 是第 i 堆原有的数量
ave 是平均数
Xi 是第 i 个人向左传递的数量

当 xi > 0 代表 这个人向左传递 xi 个
xi < 0 代表 这个人从左边借 xi 个

那么 满足 A i + x i + 1 − x i = a v e Ai + x_{i+1}-x_i = ave Ai+xi+1​−xi​=ave
移项 A i + x i + 1 − a v e = x i Ai + x_{i+1} - ave = x_i Ai+xi+1​−ave=xi​
是否移动我们只要看每次 x i x_i xi​ 是否为 0 即可

这个式子里我们不知道的就是 x i + 1 x_{i+1} xi+1​

x i + 1 x_{i+1} xi+1​ 所代表的就是前 i 项与均值的差值的和 ， 维护一个前缀和即可

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e3+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;ll n,sum,ave,ans;
ll a[N];
ll c[N];int main(){IOS;cin >> n;for(int i=1;i<=n;i++){cin >> a[i];sum += a[i];}ave = sum / n;for(int i=1;i<=n;i++){c[i] = -(a[i] - ave) + c[i-1];a[i] = a[i] - ave + c[i];if(a[i]) ans++;}cout<< ans;return 0;
}

K 糖果传递

这题是一个环形的均分纸牌

上题的假设不变

我们假设 Ai 是第 i 堆原有的数量
ave 是平均数
Xi 是第 i 个人向左传递的数量

当 xi > 0 代表 这个人向左传递 xi 个
xi < 0 代表 这个人从左边借 xi 个

那么 满足 A i + x i + 1 − x i = a v e Ai + x_{i+1}-x_i = ave Ai+xi+1​−xi​=ave

我们要求的答案就是 ∑ i = 1 n x i \sum_{i=1}^{n}x_i ∑i=1n​xi​

A 1 + x 2 − x 1 = a v e A_1 + x_2-x_1 = ave A1​+x2​−x1​=ave
A 2 + x 3 − x 2 = a v e A_2 + x_3-x_2 = ave A2​+x3​−x2​=ave
A 3 + x 4 − x 3 = a v e A_3 + x_4-x_3 = ave A3​+x4​−x3​=ave

A n + x 1 − x n = a v e A_n + x_1-x_n = ave An​+x1​−xn​=ave

整理一下

x 2 = x 1 + a v e − A 1 x_2 = x_1 +ave -A_1 x2​=x1​+ave−A1​
x 3 = x 2 + a v e − A 2 x_3 = x_2 +ave -A_2 x3​=x2​+ave−A2​

x n = x n − 1 + a v e − A n − 1 x_n = x_{n-1} +ave -A_{n-1} xn​=xn−1​+ave−An−1​

把所有项用 x 1 x_1 x1​表示
x 1 = x 1 x_1 = x_1 x1​=x1​
x 2 = x 1 + a v e − A 1 x_2 = x_1 +ave -A_1 x2​=x1​+ave−A1​
x 3 = x 1 + a v e − A 2 + a v e − A 1 x_3 = x_1 +ave -A_2+ave-A_1 x3​=x1​+ave−A2​+ave−A1​

x n = x 1 − ∑ j = 1 i − 1 A j − a v e x_n = x_1-\sum_{j=1}^{i-1}{A_j-ave} xn​=x1​−∑j=1i−1​Aj​−ave

c i = { 0 if  x = 1 ∑ j = 1 i − 1 A j − a v e if  x > 1 c_i=\begin{cases} 0& \text{ if } x=1 \\ \sum_{j=1}^{i-1}{A_j-ave}& \text{ if } x>1 \end{cases} ci​={0∑j=1i−1​Aj​−ave​ if x=1 if x>1​

x n = x 1 − c i x_n = x_1-c_i xn​=x1​−ci​

a n s = ∑ i = 1 n ∣ x 1 − c i ∣ ans = \sum_{i=1}^{n}{|x_1-c_i|} ans=∑i=1n​∣x1​−ci​∣

注意要加绝对值 ， c i c_i ci​ 明显是不变的 ，只要确定 x 1 x_1 x1​的值即可 ，整个图结构是环形的 ，可以取任意一个值作为 x 1 x_1 x1​ 要使整个答案最小

货舱选址问题 ， 选中间的那个数

#include
using namespace std;#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;ll n,sum,ave,ans;
ll a[N];
ll c[N];int main(){IOS;cin >> n;for(int i=1;i<=n;i++){cin >> a[i];sum += a[i];}ave = sum / n;for(int i=2;i<=n;i++){c[i] = c[i-1] + a[i-1] - ave;}sort(c+1,c+1+n);int now = c[(n+1)/2];for(int i=1;i<=n;i++){ans += abs(now - c[i]);}cout << ans;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！