ARTICLE · 1085887
GESP 2026年9月 C++ 五级真题,答案与知识点解析
一、单选题（每题 2 分，共 30 分）
第 1 题
小杨用单链表保存任务序列，并同时维护头指针 head 和尾指针 tail。在链表非空且已知 tail 的情况下，在表尾插入新结点的时间复杂度是（ ）。
struct Node {
int value;
Node *next;
};
Node *head;
Node *tail;
A. $O(1)$
B. $O(\log n)$
C. $O(n)$
D. $O(n \log n)$
答案：A
知识点解析
本题考查链表的插入操作与时间复杂度分析。由于同时维护了尾指针 tail，在表尾插入新结点只需固定几步：让 tail->next 指向新结点、再修改 tail 指向新结点，操作次数与链表长度 n 无关，时间复杂度为 O(1)。若只维护头指针 head，则需要从头遍历到表尾才能插入，才是 O(n)。B、C、D 对应的都是需要遍历部分或全部结点的操作，与本题“已知 tail”的前提不符。
第 2 题
在不带哨兵结点的双向链表中，结点 p 既不是头结点也不是尾结点。删除 p 的正确代码是（ ）。
struct Node {
int value;
Node *prev;
Node *next;
};
A.
p->prev = p->next;
p->next = p->prev;
delete p;
B.
p->prev->next = p;
p->next->prev = p;
delete p;
C.
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
D.
p->next = p->prev;
p->prev->next = nullptr;
delete p;
答案：C
知识点解析
本题考查双向链表结点的删除操作。删除 p 的关键是修改 p 两个邻居的指针：让前驱的 next 指向 p 的后继（p->prev->next = p->next），再让后继的 prev 指向 p 的前驱（p->next->prev = p->prev），最后 delete p，C 选项正是这一写法。A 选项只修改了 p 自身的指针，两个邻居仍指向 p，且第二行在第一行之后取到的 p->prev 已经被改坏，等于没删；B 选项方向写反，让邻居重新指向 p 自身；D 选项逻辑混乱，会把链表截断。
第 3 题
下面函数使用快慢指针查找单链表的中间结点。横线处应填写（ ）。
struct Node {
int value;
Node *next;
};
Node *middle(Node *head) {
Node *slow = head;
Node *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
______________________
}
return slow;
}
A. fast = fast->next;
B. fast = fast->next->next;
C. fast = slow->next;
D. fast = head->next;
答案：B
知识点解析
本题考查快慢指针求链表中间结点的技巧。slow 每次走 1 步，fast 每次走 2 步，当 fast 到达末尾时 slow 恰好停在中间，故应填 fast = fast->next->next。A 选项 fast 每次也走 1 步，两指针永远重合；C、D 选项没有让 fast 相对 slow 以两倍速度持续前进，无法形成“快慢”效果。循环条件 fast != nullptr && fast->next != nullptr 保证了走两步之前两个结点都存在，不会解引用空指针。
第 4 题
函数 gcd(int a, int b) 定义如下，则 gcd(105, 45) 的结果是（ ）。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
A. 3
B. 5
C. 15
D. 45
答案：C
知识点解析
本题考查辗转相除法（欧几里得算法）求最大公约数。模拟递归过程：gcd(105, 45) → gcd(45, 105 % 45) = gcd(45, 15) → gcd(15, 45 % 15) = gcd(15, 0) = 15。验证：105 = 15 × 7，45 = 15 × 3，15 确为最大公约数。A（3）、B（5）虽然也是两者的公约数，但不是最大的；D（45）不能整除 105，根本不是公约数。
第 5 题
下面函数用于判断正整数 n 是否为质数。横线处的最佳写法是（ ）。
bool isPrime(int n) {
if (n < 2)
return false;
for (int i = 2; __________________; i++) {
if (n % i == 0)
return false;
}
return true;
}
A. i < n
B. i <= n / 2
C. i * i < n
D. (long long) i * i <= n
答案：D
知识点解析
本题考查质数判断中“试除到 √n”的优化与整数溢出问题。若 n 有大于 √n 的因子，必有对应小于 √n 的因子，故只需试除到 i * i <= n。C 选项用了严格小于 i * i < n，当 n 是完全平方数（如 n = 9，i = 3 时 3 × 3 == 9）会漏判，把 9 误判成质数；A、B 选项判断结果虽正确，但要试除到 n/2 甚至 n - 1，效率低。D 选项既用 <= 保证正确性，又把 i 转成 long long 后再相乘，防止 i * i 超出 int 范围溢出，是最佳写法。
第 6 题
下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次，横线处应填写（ ）。
vector<int> linearSieve(int n) {
vector<bool> composite(n + 1, false);
vector<int> primes;
for (int i = 2; i <= n; i++) {
if (!composite[i])
primes.push_back(i);
for (int p : primes) {
if ((long long)i * p > n)
break;
composite[i * p] = true;
if (__________________)
break;
}
}
return primes;
}
A. p % i == 0
B. i % p == 0
C. i == p
D. i * p == n
答案：B
知识点解析
本题考查线性筛（欧拉筛）的核心原理：每个合数只被其最小质因子筛掉一次。当遍历到的质数 p 满足 i % p == 0 时，说明 p 是 i 的最小质因子，此时若继续用更大的质数 p‘ 去筛 i × p’，则 i × p‘ 的最小质因子仍是 p，会被重复标记，因此应立即 break。例如 i = 6 时，先筛掉 6 × 2 = 12，由于 6 % 2 == 0 随即 break，避免再用 3 去筛 18（18 的最小质因子是 2，它应由 i = 9 时筛出）。A 选项条件写反了；C、D 均无法正确判断“p 已是 i 的最小质因子”这一时机。
第 7 题
根据唯一分解定理，整数 756 的正确质因数分解是（ ）。
A. $2^2 \times 3^3 \times 7$
B. $2^3 \times 3^2 \times 7$
C. $2^2 \times 3^3 \times 21$
D. $2 \times 3^3 \times 14$
答案：A
知识点解析
本题考查唯一分解定理：每个大于 1 的整数都能唯一地分解为若干质数的乘积。对 756 逐步分解：756 = 2 × 378 = 2² × 189 = 2² × 3 × 63 = 2² × 3³ × 7，验证 4 × 27 × 7 = 756，A 正确。B 选项 2³ × 3² × 7 = 504，数值就不对；C 选项 2² × 3³ × 21 = 2268，数值也不对；D 选项的乘积虽恰好等于 756，但其中 14 是合数而非质数，没有分解到全为质数，同样不是正确的质因数分解。
第 8 题
函数 f(int n) 定义如下，则 f(4) 的结果是（ ）。
int f(int n) {
if (n == 1)
return 1;
return n + f(n - 1);
}
A. 4
B. 7
C. 9
D. 10
答案：D
知识点解析
本题考查递归函数的求值。f(n) = n + f(n-1)，边界 f(1) = 1，实际就是求 1 + 2 + … + n。逐层展开：f(2) = 2 + f(1) = 3，f(3) = 3 + f(2) = 6，f(4) = 4 + f(3) = 10。也可用等差数列求和公式 4 × 5 ÷ 2 = 10 验证，故选 D。A（4）、B（7）、C（9）均是漏加部分项得到的结果，并非正确的求和值。
第 9 题
在升序数组中查找第一个严格大于 x 的元素位置，下面代码中的横线应填写（ ）。
int upperBound(const vector<int> &a, int x) {
int l = 0, r = (int)a.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (__________________) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
A. a[mid] < x
B. a[mid] >= x
C. a[mid] <= x
D. a[mid] > x
答案：C
知识点解析
本题考查二分查找中 upper_bound（第一个严格大于 x 的位置）的写法。代码模板中 if 分支执行 l = mid + 1，说明条件成立时 mid 一定不是答案、可以放心排除，因此条件应是 a[mid] <= x（等于 x 的也不满足“严格大于”）；条件不成立即 a[mid] > x 时，mid 本身可能就是答案，执行 r = mid 保留它，C 正确。若填 A（a[mid] < x），等于 x 的元素会落入 else 分支被 r = mid 保留，求出的将是第一个大于等于 x 的位置（lower_bound），与题意不符；B 恰与正确逻辑相反；D 的条件方向与 if/else 的动作搭配颠倒。
第 10 题
小杨需要把若干箱货物按原顺序分配到 days 天中，每天运输连续的若干箱，求能够完成任务的最小载重量。函数 check(cap) 判断载重量为 cap 时能否在规定天数内运完。横线处应填写（ ）。
long long l = maxWeight;
long long r = totalWeight;
while (l < r) {
long long mid = l + (r - l) / 2;
if (check(mid)) {
____________________
} else {
____________________
}
}
cout << l;
A. l = mid + 1; 和 r = mid;
B. r = mid; 和 l = mid + 1;
C. r = mid - 1; 和 l = mid;
D. l = mid; 和 r = mid - 1;
答案：B
知识点解析
本题考查二分答案求“最小可行载重量”。check(cap) 为真表示载重量 cap 能在规定天数内运完，且 cap 越大越容易满足，可行性具有单调性，可以二分。由于求最小的可行值：当 check(mid) 为真时，mid 本身可能就是答案，应执行 r = mid 保留它；为假时 mid 太小，应执行 l = mid + 1 排除。B 正确。A 把两个动作对调，会在可行时跳过答案；C、D 中 r = mid - 1、l = mid 这类更新方式与“l < r 收敛到同一点”的模板不匹配，容易漏掉答案或死循环。
第 11 题
下面是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写（ ）。
while (i <= mid && j <= right) {
if (__________________) {
temp.push_back(a[i++]);
} else {
temp.push_back(a[j++]);
}
}
A. a[i] < a[j]
B. a[i] > a[j]
C. a[i] >= a[j]
D. a[i] <= a[j]
答案：D
知识点解析
本题考查归并排序的稳定性。稳定性要求值相等的元素排序后保持原有相对顺序，因此合并两个有序区间时，若 a[i] == a[j]，应优先取左半边的 a[i]（它原本位置更靠前），条件须用 a[i] <= a[j]，D 正确。C 选项 a[i] >= a[j] 会在相等时取右半边的元素，破坏稳定性；A 选项 a[i] < a[j] 同样把相等的情况让给了右半边；B 选项方向完全颠倒，合并出的是降序序列。
第 12 题
下面快速排序的划分函数以 a[right] 为枢轴，并把不大于枢轴的元素移动到左侧。横线处应填写（ ）。
int partition(int a[], int left, int right) {
int pivot = a[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (__________________) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[right]);
return i + 1;
}
A. a[j] <= pivot
B. a[j] > pivot
C. a[i] <= pivot
D. a[right] < a[j]
答案：A
知识点解析
本题考查快速排序 partition（划分）过程的实现。划分的目标是把不大于枢轴 pivot 的元素都移到左侧：扫描时若 a[j] <= pivot，就把它交换到左区末尾（i 先自增再 swap），扫描结束后枢轴与 a[i+1] 交换归位，A 正确。B 选项 a[j] > pivot 会把大于枢轴的元素移到左边，方向反了；C 选项比较的是 a[i] 而不是当前待判断的 a[j]，逻辑错误；D 选项 a[right] < a[j] 等价于 a[j] > pivot，与 B 犯同样的错误。
第 13 题
小杨要在一个教室安排尽可能多场活动，每场活动具有开始时间 start 和结束时间 end。采用贪心算法时，正确的选择策略是（ ）。
struct Activity {
int start;
int end;
};
A. 每次选择开始时间最早的活动
B. 每次选择持续时间最短的活动
C. 每次选择参与人数最少的活动
D. 按结束时间从早到晚排序，依次选择与已选活动不冲突的活动
答案：D
知识点解析
本题考查活动安排问题（区间调度）的贪心策略。要选出最多的互不冲突活动，正确做法是按结束时间从早到晚排序，每次选结束最早且与已选活动不冲突的活动——结束越早，给后面活动留出的时间越多，可以证明该策略得到的活动数最多。A 选项开始最早的活动可能持续很久，反而占用大量教室时间；B 选项最短的活动可能开始得很晚（如排在一天末尾），错过前面的机会；C 选项参与人数与能安排多少场活动无关。
第 14 题
下面函数使用迭代方法求最大连续子段和。对于数组 {-2, 3, -1, 5, -6, 2}，函数返回值是（ ）。
int maxSubArray(const vector<int> &a) {
int best = a[0];
int current = a[0];
for (int i = 1; i < (int)a.size(); i++) {
current = max(a[i], current + a[i]);
best = max(best, current);
}
return best;
}
A. 5
B. 6
C. 7
D. 8
答案：C
知识点解析
本题考查最大连续子段和的动态规划解法（Kadane 算法）。current 表示以当前元素结尾的最大子段和，转移为 current = max(a[i], current + a[i])，best 记录全局最大值。对 {-2, 3, -1, 5, -6, 2} 逐步演算：current 依次为 -2、3（3 优于 -2+3=1）、2、7（2+5）、1、3；best 依次为 -2、3、3、7、7、7。最大子段和为 7，对应子段 {3, -1, 5}，故选 C。A、B、D 均是演算过程中的中间值或错误组合。
第 15 题
数组 a 和 b 按低位在前的顺序保存两个非负大整数。下面代码实现高精度加法，横线处应填写（ ）。
vector<int> add(const vector<int> &a, const vector<int> &b) {
vector<int> c;
int carry = 0;
int n = max(a.size(), b.size());
for (int i = 0; i < n; i++) {
int sum = carry;
if (i < a.size())
sum += a[i];
if (i < b.size())
sum += b[i];
c.push_back(sum % 10);
____________________
}
if (carry)
c.push_back(carry);
return c;
}
A. carry = sum % 10;
B. carry = sum;
C. carry = sum / 10;
D. carry = c[i] / 10;
答案：C
知识点解析
本题考查高精度加法的进位处理。sum 是当前位两个数字与低位进位 carry 的总和，本位数字是 sum % 10（已 push 进 c），向高位的进位则是 sum / 10（整除丢弃余数），C 正确。A 选项 sum % 10 是本位数字而不是进位；B 选项把整个 sum（最大可接近 20）当作进位，数值错误；D 选项中 c 的末位已是 sum % 10，小于 10，再除以 10 恒为 0，进位信息丢失。
二、判断题（每题 2 分，共 20 分）
第 1 题
下面代码在已知结点 p 的情况下，能够以 $O(1)$ 的时间在单链表的 p 结点之后插入新结点 s。
s->next = p->next;
p->next = s;
答案：√
知识点解析
本题考查单链表在已知结点处的插入操作。先执行 s->next = p->next 让新结点接上 p 的后继，再执行 p->next = s 把 p 指向新结点，两步都是固定次数的指针操作，与链表长度无关，因此是 O(1)。注意两步顺序不能颠倒，否则会丢失 p 原来的后继。说法正确。
第 2 题
下面代码可以安全地删除单链表的头结点，并使 head 指向删除后的新头结点。
Node *p = head;
delete p;
head = p->next;
答案：×
知识点解析
本题考查内存释放与指针使用的顺序。代码先 delete p 释放了 head 所指结点，之后才执行 head = p->next，这属于访问已释放的内存（悬空指针），行为未定义。正确写法应先把 head 移到下一个结点再释放：Node *p = head; head = head->next; delete p;。说法错误。
第 3 题
下面欧几里得算法既适用于 a > b，也适用于 a < b，只要 a、b 是正整数。
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
答案：√
知识点解析
本题考查欧几里得算法的适用条件。当 a < b 时，第一次循环中 a % b = a（小数对大数取模等于自身），随后执行 a = b、b = r（r 即原来的 a），相当于自动交换了两个数，之后按 a > b 的正常流程执行。例如 gcd(45, 105)：r = 45，a 变为 105，b 变为 45，等价于进入 gcd(105, 45)。因此只要 a、b 是正整数，该算法都适用。说法正确。
第 4 题
下面埃氏筛从 i * i 开始标记，是因为 i * i 之前的 i 的合数倍数已经被更小的质因子标记过。
for (int i = 2; (long long)i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
答案：√
知识点解析
本题考查埃氏筛从 i * i 开始标记的原因。对质数 i 而言，2i、3i、……、(i-1)·i 这些倍数都含有比 i 更小的质因子（如 3i 含因子 3），早已在处理更小质数时被标记过，从 i * i 开始才可能有“首次”标记，既不遗漏也不重复。例如 i = 5 时，10、15、20 已分别被 2 和 3 标记过。说法正确。
第 5 题
下面程序的时间复杂度为 $O(n)$。
for (int i = 1; i <= n; i *= 2) {
cout << i << endl;
}
答案：×
知识点解析
本题考查循环变量倍增的时间复杂度分析。i 从 1 开始每轮乘 2，执行次数约为 log₂n + 1（如 n = 1024 时只输出 1、2、4、…、1024 共 11 行），因此时间复杂度是 O(log n) 而不是 O(n)。判断复杂度时要看循环变量的增长方式，而不是简单看一层 for 循环。说法错误。
第 6 题
若数组 a 已按升序排列，下面函数能够返回最后一个小于等于 x 的元素下标；如果不存在，则返回 -1。
int findLastLE(const vector<int> &a, int x) {
int l = 0, r = (int)a.size() - 1;
int ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
答案：√
知识点解析
本题考查二分查找求“最后一个小于等于 x 的下标”。当 a[mid] <= x 时，mid 可能是答案，先记录 ans = mid，再令 l = mid + 1 继续向右寻找更大的合法下标；当 a[mid] > x 时令 r = mid - 1 向左收缩。循环结束时 ans 保存的是最后一次记录的、最靠右的满足条件的下标；若没有任何元素满足条件，ans 保持初值 -1。说法正确。
第 7 题
快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为 $O(n \log n)$。
答案：×
知识点解析
本题考查快速排序最坏情况的分析。若每次选区间第一个元素作枢轴，当输入已经升序时，枢轴恰是最小元素，划分后左半部分为空、右半部分有 n-1 个元素，递归深度达到 n 层，总比较次数约为 n(n-1)/2，最坏时间复杂度为 O(n²) 而非 O(n log n)。常用的规避方法有随机选取枢轴、三数取中等。说法错误。
第 8 题
归并排序的递推式为 $T(n) = 2T(n/2) + O(n)$，对应的时间复杂度为 $O(n \log n)$。
答案：√
知识点解析
本题考查归并排序复杂度的递推分析。归并排序把数组分成两半分别排序（代价 2T(n/2)），再把两个有序半段线性合并（代价 O(n)）。逐层展开：共 log n 层，每层合并的总代价为 O(n)，由主定理（或直接求和）得 T(n) = O(n log n)。说法正确。
第 9 题
下面的贪心代码一定能对任意硬币面值集合 coins 求出 money 所需的最少硬币数。
int count = 0;
for (int coin : coins) { // coins 按面值从大到小排列
count += money / coin;
money %= coin;
}
答案：×
知识点解析
本题考查贪心算法求解凑硬币问题的适用范围。从大到小贪心只在特殊面值体系（如人民币面额）下正确，对任意面值集合不保证最优。反例：面值为 {1, 3, 4}，money = 6，贪心先取 4，再取两个 1，共 3 枚；而最优解是 3 + 3，只需 2 枚。要保证任意面值都最优，需使用动态规划。说法错误。
第 10 题
假设两个非负高精度整数分别存储在数组 a 和 b 中，且 a ≥ b。数组采用低位在前的方式存储，即 a[0] 表示个位。下面代码中的 c 可以正确保存 a - b 的各位数字。
int borrow = 0;
for (int i = 0; i < len; ++i) {
int t = a[i] - b[i] + borrow;
if (t < 0) {
t += 10;
borrow = 1;
} else {
borrow = 0;
}
c[i] = t;
}
答案：×
知识点解析
本题考查高精度减法的实现细节。借位处理逻辑本身正确（t < 0 时加 10 并向高位借 1，且 a ≥ b 保证最终无剩余借位），但代码中 b[i] 直接按统一长度 len 访问：当 b 的位数小于 len 时，b 的高位并不存在，b[i] 会越界访问未定义的内存，结果不可靠。正确做法是先把 a、b 补齐到相同长度（高位补 0），或访问前判断 i 是否小于 b 的实际长度，不足按 0 处理。说法错误。
三、编程题（每题 25 分，共 50 分）
哥德巴赫猜想
时间限制 1.0 s 内存限制 512.0 MB
题目描述
众所周知，哥德巴赫猜想是说，任何大于 2 的偶数都能写成两个质数（素数）之和。例如：
- 4 = 2 + 2
- 6 = 3 + 3
- 8 = 3 + 5
- 10 = 3 + 7 = 5 + 5
聪明的你肯定想知道，对于大于 2 的偶数 n，它有多少种写成两个质数之和的方法。例如 4、6 和 8 都只有一种方法，10 有两种方法。请你编写程序计算这个问题的答案。
在本题中，我们认为两种方案不同，当且仅当两种分解方案包含的素数互不相同；即 10 = 3 + 7 和 10 = 7 + 3 是同一种方案，不能重复计数。
输入格式
一行，一个大于 2 的偶数 n。
输出格式
一行，一个整数，表示将 n 写成两个质数之和的方法数。
样例
4
1
10
2
数据范围
对于 40% 的测试点，保证 4 ≤ n ≤ 100。
对于所有测试点，保证 4 ≤ n ≤ 10⁶。
参考程序（答案）
#include <cassert>
#include <cstdio>
using namespace std;
int n, ans;
bool not_prime[1000005];
int primes[500000], pcnt = 0;
void get_primes() {
not_prime[1] = true;
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
primes[pcnt++] = i;
for (int j = 2; i * j <= n; ++j) {
not_prime[i * j] = true;
}
}
}
}
int main() {
scanf("%d", &n);
get_primes();
for (int i = 0; i < pcnt && primes[i] <= n / 2; ++i)
if (!not_prime[n - primes[i]])
ans++;
printf("%d\n", ans);
return 0;
}
饮品调制
时间限制 1.0 s 内存限制 512.0 MB
题目描述
你想调制一份甜度恰到好处的饮品给你的朋友们品尝。
有 n 种原料可供用于调制饮品。第 i 种原料存量有 $v_i$ 升，每升含有 $s_i$ 克糖分。你可以自由选择原料加入饮品，但每种原料的使用量不得超过其剩余存量。也就是说，假设第 i 种原料选用 $k_i$ 升，应当有 $0 \le k_i \le v_i$，$k_i$ 可以取 0 到 $v_i$ 之间的任何数字（包括小数）。
一份甜度恰到好处的饮品需要保证甜度恰好为 t。最终你调制得到的饮品甜度将为 $\frac{\sum_{i=1}^{n} k_i s_i}{\sum_{i=1}^{n} k_i}$。为了让更多的朋友喝到饮品，请问最多能调制出多少升甜度恰到好处的饮品？如果无法调制出甜度恰到好处的饮品，则认为答案是 0。
输入格式
第一行，两个整数 n, t，分别表示原料种类数量，恰到好处的甜度。
接下来 n 行，每行两个整数 $v_i, s_i$，分别表示第 i 种原料的存量体积，每升含有的糖分质量。
输出格式
一行，一个小数，表示能调制出的甜度恰到好处的饮品最大体积，保留三位小数。
样例
4 2
6 1
5 2
8 5
1 0
14.667
2 5
3 4
5 3
0.000
数据范围
对于 40% 的测试点，保证 n = 2。
对于所有测试点，保证 1 ≤ n ≤ 2000，0 ≤ t ≤ 200，1 ≤ $v_i$ ≤ 100，0 ≤ $s_i$ ≤ 200。
参考程序（答案）
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2005;
int n, t;
int v[N], s[N], p[N];
double ans;
bool cmp(int x, int y) {
return s[x] < s[y];
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &v[i], &s[i]);
p[i] = i;
}
sort(p + 1, p + n + 1, cmp);
int ss = 0, sv = 0;
for (int i = 1; i <= n; i++) {
int cv = v[p[i]], cs = s[p[i]];
if (ss + cs * cv > t * (sv + cv)) {
double k = (double)(t * sv - ss) / (cs - t);
ans = max(ans, sv + k);
break;
}
ss += cs * cv;
sv += cv;
}
if (ss == sv * t) ans = max(ans, (double) sv);
sv = ss = 0;
for (int i = n; i >= 1; i--) {
int cv = v[p[i]], cs = s[p[i]];
if (ss + cs * cv < t * (sv + cv)) {
double k = (double)(t * sv - ss) / (cs - t);
ans = max(ans, sv + k);
break;
}
ss += cs * cv;
sv += cv;
}
if (ss == sv * t) ans = max(ans, (double) sv);
printf("%.3lf\n", ans);
return 0;
}
由于工作量较大，若存在错漏欢迎大家评论区指正。祝各位考生顺利通过！觉得有用，欢迎点赞、在看、转发三连。