样例过了
by y6hz @ 2023-06-07 20:39:38
if (a[j].v/a[j].t>a[j-1].v/a[j-i].t)这一行
这里下标j-i可能会小于0,数组下标小于0会RE的
by Morre @ 2023-06-07 20:54:31
@[Morre](/user/233896) 谢谢提醒!1写成i了
by y6hz @ 2023-06-07 21:18:15
另外,此题用贪心算法无法保证正确性,可以举一个反例:
| id | 0 | 1 | 2 |
| :----------: | :----------: | :----------: | :----------: |
| value | 6 | 10 | 12 |
| time | 1 | 2 | 3 |
| value/time | 6 | 5 | 4 |
当T=5时,显然取1和2有最大价值22,而贪心算法会取0和1,给出错误答案16
此题的正确做法是动态规划算法,这题也是动态规划的经典模板题,如果不会的话可以学习一下题解
by Morre @ 2023-06-07 21:23:34
楼上表格格式乱了,将就看下QAQ
by Morre @ 2023-06-07 21:24:22