#创作计划# 快速获得时间刺客教程
2025-08-21 08:33:48
发布于：上海
312阅读
0回复
0点赞
本期帖子我来做一下快速获得时间刺客的教程。众所周知，时间刺客非常难得，需要时间复杂度超越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].piece*maxTake;
now+=box[i].weight*maxTake;
}
}
cout<<ans;
return 0;
}
我实际上是修改了沙老师（你们可以在这道题的题解里发现这个人，他的代码运行出来编译错误）的代码，如果想要完全理解，我建议去看看沙老师的描述（在题解里可以找到）。
但是，因为刷题人数逐渐增加，我无法保证这段代码可以永久达到100%超越，想看更优化的代码可以关注沙老师，我一定会向他催更的。
以上为快速获得时间刺客的教程，如果有不懂的部分，欢迎在评论区或者我主页提问，我将会回答。
全部评论 14
现在的人可以用我这个快读快写
namespace FastIO { const int SZ = 1 << 20; char inbuf[SZ], outbuf[SZ]; int in_left = 0, in_right = 0; int out_right = 0; inline void load() { int len = fread(inbuf, 1, SZ, stdin); in_left = 0; in_right = len; } inline char getchar() { if (in_left >= in_right) load(); if (in_left >= in_right) return EOF; return inbuf[in_left++]; } inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); } return x * f; } inline void flush() { fwrite(outbuf, 1, out_right, stdout); out_right = 0; } inline void putchar(char ch) { outbuf[out_right++] = ch; if (out_right == SZ) flush(); } inline void write(int x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } struct Flusher { ~Flusher() { flush(); } } flusher; } using FastIO::read; using FastIO::write; using FastIO::putchar;2025-08-21 来自 上海
1要不跟你们说一下我时间，空间是咋得的：
一个俸∑釼蠡的一天，我随便找几题AK我也不知道咋回事，几道题里面有两道题空间和时间超过了100%的用户，我也不知道是为哈2025-07-31 来自 江苏
0
有帮助，赞一个