首页 > 试题广场 >

小红笔试

[编程题]小红笔试
  • 热度指数：325 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红正在参加一场编程笔试，整场考试共有 n 道编程题。每道题包含若干测试用例，通过的用例数量与该题得到的分数成正比。

\hspace{15pt}对于第 i 道题，小红有三种选择：
\hspace{23pt}\bullet\, 写出暴力算法：耗时 t_{i,b}，可获得 s_{i,b} 分；
\hspace{23pt}\bullet\, 写出正确算法：耗时 t_{i,a}，可获得满分 s_{i,a}；
\hspace{23pt}\bullet\, 放弃此题：不耗时且得分为 0。

\hspace{15pt}已知 t_{i,b}\leqq t_{i,a} 且 s_{i,b}\leqq s_{i,a}。现给定笔试的总时长为 T，请你为小红规划做题方案，使得在不超过 T 分钟的前提下，总得分最大。

输入描述:
\hspace{15pt}第一行输入两个正整数 n,T\ \left(1\leqq n,T\leqq2000\right)——题目数量与笔试总时长。

\hspace{15pt}接下来 n 行，第 i 行输入四个正整数 t_{i,a},\ s_{i,a},\ t_{i,b},\ s_{i,b}（1\leqq t_{i,b}\leqq t_{i,a}\leqq2000，1\leqq s_{i,b}\leqq s_{i,a}\leqq10^5），含义如下：
\hspace{23pt}\bullet\, t_{i,a}：写出正确算法的耗时；
\hspace{23pt}\bullet\, s_{i,a}：正确算法得分；
\hspace{23pt}\bullet\, t_{i,b}：写暴力算法的耗时；
\hspace{23pt}\bullet\, s_{i,b}：暴力算法得分。


输出描述:
\hspace{15pt}输出一个长度为 n 的字符串，第 i 个字符表示第 i 题的策略：
\hspace{23pt}\bullet\, 字符 \tt A——编写正确算法；
\hspace{23pt}\bullet\, 字符 \tt B——编写暴力算法；
\hspace{23pt}\bullet\, 字符 \tt F——放弃此题。

\hspace{15pt}要求输出方案的总耗时不超过 T，且总得分尽可能大。若存在多种方案能取得最高分，输出任意一种皆可。
示例1

输入

3 10
4 10 2 5
4 20 2 5
6 20 1 15

输出

AAB

说明

\hspace{15pt}选择策略 \tt AAB：
\hspace{23pt}\bullet\, 题 1 写正确算法，耗时 4，得分 10；
\hspace{23pt}\bullet\, 题 2 写正确算法，耗时 4，得分 20；
\hspace{23pt}\bullet\, 题 3 写暴力算法，耗时 1，得分 15。

\hspace{15pt}总耗时 4+4+1=9\leqq T，总得分 10+20+15=45，可以证明该得分已达到最优。
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-01 12:27:38
HIGH90 小红笔试 题目描述 小红参加一场有 道题的编程笔试，总时长为 分钟。对于第 道题，她有三种选择： 写出正确算法：耗时 ，得分 。 写出暴力算法：耗时 ，得分 。 放弃此题：耗时 ，得分 。 要求规划一个做题方案，使得在总耗时不超过 的前提下，总得分最大。并输出这个方案。 展开全文
去ta的博客 赞 (4) 回复(1) 收起

问题信息

难度：
1条回答 70浏览

热门推荐

相关试题

小红笔试

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号