针对数据的特殊性,设计算法
2021/11/30 11:06:11
本文主要是介绍针对数据的特殊性,设计算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
在我的理解中,许多计算机算法是针对某个特殊的问题来设计算法,也就是说这个问题并不是“普适”,而它的特殊性就体现在数据的范围上,所以我们应该提高对数据的敏感度,寻找合适的突破口来解决整个问题。以下面这个问题为例:
堆蛋糕
其实小布是一个十分犀利的蛋糕师。他最喜欢的食物就是蛋糕。一天,他自己做出了N个圆柱状的蛋糕,每个蛋糕 都有一个底面圆的半径Ri。高度都是一样的。小布在开始享用他的蛋糕大餐之前忽然觉得,圆柱状的蛋糕没有什么 诱惑力。小布看到了别人结婚用的蛋糕都是很多很多层的,那样的蛋糕才比较给力。但是堆太多层的蛋糕比较困难 ,于是小布想要堆出许多三层的蛋糕,再开始自己的蛋糕大餐。当然,作为蛋糕师,小布在堆蛋糕的时候不会对蛋 糕的形状有任何破坏,而且,小布希望三层蛋糕的半径从上往下严格递增。这才是一个普通的好蛋糕。但是小布在 考虑一个十分重要的问题,最多可以堆出多少三层蛋糕呢?
Input
输入第一行仅包含一个整数N,表示蛋糕的数量。
接下来N个整数,表示每个蛋糕半径的大小Ri。
N<=3,000,000 Ri<=N
Output
输出一行仅包含一个整数,表示最多可以做成多少个蛋糕
Samples
输入数据 1
6
1 2 3 4 3 2
输出数据 1
2
拿到问题后,我们可以发现以下几个问题:
1:N小于等于3e6,这就说明N平方的算法是不可能通过的。
2:蛋糕半径R小于3e6,这就意味着我们可能对R进行桶排,找出某个半径出现的次数。
3:每个蛋糕只堆3层,3是一个比较小的数字了。
4:蛋糕的组成,只要3层的半径呈现一个递增的数列就好了。
于是拿样例来看,我们可以先统计出每种半径出现的次数,得到如下结果
半径值 1 2 3 4
出现次数 1 2 2 1
接下来本题最关键的点到了,我们如何完成数字之间的配对。也就是说
如果我们让半径值为(1,2,4)组成一个蛋糕后,剩下的半径值为(2,3,3),就再不能组成新的蛋糕了,而事实上我们可以组成(1,2,3),(2,3,4)这2个蛋糕出来。也就是说由于每种半径出现的次数是不一样的,此时为了组成尽可能多的蛋糕,我们应该尽量先使用次数较多的数字,而不是使用出现次数较小的,因为这样会导致后期会现有蛋糕的数量较多,但种类却没有3种的尴尬局面。
总结本题求解过程:
1:求出每个半径出现的次数,由于每次都要找出出现次数最大的3个数字,所以我们可以将其丢到大根堆中。
2:不断从堆中取出3个数字a,b,c出来,并且a>=b>=c,于是可能组成c个蛋糕出来。
3:将没有用完的蛋糕丢回堆中,即a-c与b-c的值.
4:重复执行(2),(3)步骤直至堆中的元素不足3类。
代码如下:
#include<bits/stdc++.h> using namespace std; int n,x,kinds,k1,k2,k3,ans=0; int num[3000010]={0}; priority_queue<int>d; int main() { scanf("%d",&n); kinds=0; for(int i=1;i<=n;i++) { scanf("%d",&x); num[x]++; } for(int i=1;i<3000010;i++) if(num[i]>0) d.push(num[i]); while(d.size()>=3) { k1=d.top(); d.pop(); k2=d.top(); d.pop(); k3=d.top(); d.pop(); k1=k1-k3; k2=k2-k3; if(k1>0) d.push(k1); if(k2>0) d.push(k2); ans=ans+k3; k3=0; } printf("%d",ans); return 0; }
然而当我再拿到这个题时,我的思维又被打开了.
组建部门
EYENCE有N个部门,其中A i员工属于第i个部门(1≤i≤N)。没有员工属于多个部门。 该公司正在计划跨部门的项目。每个项目将由从K个不同部门中,每个部门选出一个人,共K名员工组成。 最多可以做多少个项目?没有员工可以参与多个项目
Input
第一行给出N,K 接下来给出N个数字,代表a1....an
1≤K≤N≤2×10^5
1≤Ai≤10^12
Output
如题
样例输入
3 3
2 3 4
样例输出
2
题解:这个题与上一个题大同小异,都是不断一个数列中取出权值最大的K个数字,设为
a1,a2,a3....ak且a1>=a2>=a3>=....aK.然后再将a1-ak,a2-ak,a3-ak.....的值丢回原数列。
但上个题中因为K的值较小,我们可以用堆来完成,此题K的值很大,明显不适合做为突破口。
这篇关于针对数据的特殊性,设计算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南