快速获得时间刺客教程
2025-07-17 11:38:50
发布于：上海
本期帖子我来做一下快速获得时间刺客的教程。众所周知，时间刺客非常难得，需要时间复杂度超越99%的人。
所以开始教程，首先点击acgo左上角题库，进去之后找到知识点那一栏，点击它，然后再点动态规划，选择背包动态规划，进去后划到最底部，点击数字2，在题目里找到宝物筛选点进去，就完成了第一部分。
这道题是一道典型的贪心（其实用01背包也可以，但因为这题范围不大，所以也可以用贪心），但是直接硬写的话时间复杂度非常之高，远远达不到时间刺客的需求，所以对代码进行优化，使得时间复杂度最低。优化代码如下：
#include<bits/stdc++.h>
using namespace std;
struct info
{
int piece;
int weight;
int num;
double everypiece;
};
bool cmp(info a,info b)
{
return a.everypiece>b.everypiece;
}
int main()
{
int n,total,ans=0,now=0;
cin>>n>>total;
info box[n];
for(int i=0;i<n;i++){
cin>>box[i].piece>>box[i].weight>>box[i].num;
box[i].everypiece=box[i].piece/box[i].weight;
}
sort(box,box+n,cmp);
for(int i=0;i<n&&now<total;i++){
int maxTake=min(box[i].num,(total-now)/box[i].weight);
if(maxTake>0){
ans+=box[i].piecemaxTake;
now+=box[i].weightmaxTake;
}
}
cout<<ans;
return 0;
}
我实际上是修改了沙老师（你们可以在这道题的题解里发现这个人，他的代码运行出来编译错误）的代码，如果想要完全理解，我建议去看看沙老师的描述（在题解里可以找到）。
但是，因为刷题人数逐渐增加，我无法保证这段代码可以永久达到100%超越，想看更优化的代码可以关注沙老师，我一定会向他催更的。
以上为快速获得时间刺客的教程，如果有不懂的部分，欢迎在评论区或者我主页提问，我将会回答。
全部评论 9
要不跟你们说一下我时间，空间是咋得的：
一个俸∑釼蠡的一天，我随便找几题AK我也不知道咋回事，几道题里面有两道题空间和时间超过了100%的用户，我也不知道是为哈16小时前 来自 江苏
0
有帮助，赞一个