| [洛谷][noip][算法竞赛进阶指南]小猫爬山 | 您所在的位置：网站首页 › 洛谷1012 › [洛谷][noip][算法竞赛进阶指南]小猫爬山 |
[洛谷][noip][算法竞赛进阶指南]小猫爬山
|
题目来源 洛谷
算法标签 DFS
题目简介
这道题比较好玩 我们要放猫，要自己开新的车 第一步在查找的时候，事实上你时没有车的 这个时候你只能考虑开一辆新车来放🐱 而第二次抱猫，这个时候你就需要思考了，我们唯一拥有的车子是否有剩余的空间？ 我们是该放入车里，还是新开一个车来? 每次抱一只新的猫的时候，你都需要从0到当前所有车辆的车子中考虑一遍 以下是 u为当前选择的猫 来考虑摆放在哪一个车上的思路 这是整个优化的思路 那么，我们可以直接使用贪心吗？ 我编写了一个简单的贪心的思路，检查车有没有空余，如果当前的猫能放我就放入，不能的话就开新车 #include #include using namespace std; const int N=1e5+10; int n,w; int a[N],sum[N]; int cnt; bool check(int weight)//检查猫能不能放入车内 { for(int i=1;i cin>>n>>w;//n 数量 w 每辆车的最大容量 for(int i=0;i>a[i];//读入数据 sort(a,a+n,[](int a,int b){return a>b;});//反序排序 sum[++cnt]=a[0];//初始化第一辆车 for(int i=1;ires=cnt;return ;}//如果考虑完了n只即所有猫咪，则更新答案 for(int i=0;i cin>>n>>w; res = n; for(int i=0;i>a[i]; sort(a,a+n,[](int a,int b){return a>b;});//反序排序 优化了搜索顺序 lambda表达式 dfs(0,0); cout |
我们来优化整个过程 
【本文地址】
公司简介
联系我们