作者：指针不指南吗
专栏：算法刷题

🐾或许会很慢，但是不可以停下来🐾

题目

题目链接

题解

try1代码

我的思路：单纯模拟
循环，每次取数组中最小的数，判断是否为1
为1，和最大的数合并
不为1，把最大数分成1和v[d-1]-1

res:前两个测试点过了，第三个超时

#include<bits/stdc++.h>
using namespace std;const int N=1E5+10;vector<int> v;bool cmp(int a,int b){return a>b;
}int main(){int T;cin>>T;while(T--){int n,k;//cin>>n>>k;scanf("%d %d",&n,&k);int cnt=0;v.clear();for(int i=0;i<k;i++){int x;scanf("%d",&x);v.push_back(x);}sort(v.begin(),v.end(),cmp);while(v.size()!=1){int d=v.size();if(v[d-1]==1){v[0]+=1;v.pop_back();}else{v.push_back(v[d-1]-1);v[d-1]=1;sort(v.begin(),v.end(),cmp);}cnt++;}printf("%d\n",cnt);}return 0;
}

正确题解

贪心算法
除了最后一块，剩下的全部分解成1
分解次数虽然增加了，但是合并少了（否则合并更加复杂）
cnt+=v[i]*2-1
每一块需要分解成v[i]-1
合并成成都为n的需要k-1 即v[i]-1，由于还需要和其他块合并所以+1 即v[i]
即：v[i]-1+(v[i])=2*v[i]-1

贪心策略的解释

贪心策略在这里的应用是：每次操作都尽可能减少剩余的马铃薯块数量。这样做的好处是：

1. 减少合并操作的次数：每次合并操作都会减少一块马铃薯，因此减少剩余的马铃薯块数量是减少合并操作次数的关键。
2. 灵活性：将每块马铃薯分解成多个1米长的小块，可以更灵活地进行合并操作，最终达到目标长度 ( n )。

为什么不是直接合并

直接将每块马铃薯与一块1米长的马铃薯合并的想法看似简单，但实际上并不是最优的。原因如下：

• 合并次数：如果每块马铃薯都直接与一块1米长的马铃薯合并，合并次数会等于马铃薯块的总数 ( k )。这并不是最优的，因为合并次数可以更少。
• 操作次数：将每块马铃薯分解成多个1米长的小块，虽然看起来增加了分解操作的次数，但实际上减少了合并操作的次数。最终的总操作次数会减少。

#include<bits/stdc++.h>
using namespace std;const int N=1E5+10;vector<int> v;bool cmp(int a,int b){return a>b;
}int main(){int T;cin>>T;while(T--){int n,k;//cin>>n>>k;scanf("%d %d",&n,&k);int cnt=0;v.clear();for(int i=0;i<k;i++){int x;scanf("%d",&x);v.push_back(x);}sort(v.begin(),v.end());  //保证最大的在最后 for(int i=0;i<v.size()-1;i++){  //边界 最后一个不用分解 直接+1即可 cnt+=v[i]*2-1;  }printf("%d\n",cnt);}return 0;
}

总结

认为这种题比较抽象，想不到他这种解法
将复杂的问题简单化
贪心算法，取局部最优，从而实现整体最优