题目大意

给定两个长度均为 nn 的单调不上升的序列 SS 和 PP，让 Si(1≤i≤n)S_{i}(1 \le i \le n) 中的每一个元素加上 Pj(1≤j≤n)P_{j}(1 \le j \le n)，使得原 SS 序列中的第 DD 个数经过降序排序后的排名最靠前。

解题思路

方法一（二分查找）

通过题目不难看出，如果要使 SDS_{D} 最靠前，那么要加上 P1P_{1}（因为 PP 是降序排序的）。其次，通过贪心的思想，让比 SDS_{D} 大的所有数列都加上一个最大可以使得和小于 SD+P1S_{D} + P_{1} 的数列 PjP_{j}。

由于两个序列都满足单调性，因此我们可以使用二分的思想完成：即通过每次二分查找搜索到最优解，再使用一个 bool 数组记录下已经使用过的序列数，直到用完了第二大的 PP 序列或者第 ii 个数直接大于 SD+P1S_{D} + P_{1} ，此时输出 i+1i + 1。

此时复杂度为 O(nlog⁡n)O(n \log n)。

方法二（双指针优化）

但是其实通过仔细思考发现，根本不需要通过二分查找寻找最优值，我们只需要一个指针 cur 指向当前未使用过的最大 PP 元素值。

对于第 i(1≤i≤D)i (1 \le i \le D) 个数，如果 Si+Pcur>SD+P1S_{i} + P_{cur} > S_{D} + P_{1}，那么指针向右一位，如果指针超出了界限，则跳出循环。每一次循环结束的时候就将答案减 11，同时将 cur 向右移一位。

此时复杂度仅为 O(n)O(n)。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Problem: Space Formula
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1046C
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 9;
const int INF = 0x3f3f3f3f;
int s[N], p[N];

int main()
{
    int n, pos; cin >> n >> pos;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) cin >> p[i];
        
    int maxn = s[pos] + p[1], ans = pos; // 先让答案为当前位置
    for (int i = pos - 1, cur = 2; i >= 1; i--)
    {
        while (s[i] + p[cur] > maxn && cur <= n) cur ++; // 如果条件成立，则将指针向右一位
        if (cur > n) break; // 如果指针超出界限，则终止循环
        ans --, cur ++; // 每一次循环过后更新答案和指针
    }
    
    cout << ans << '\n'; // 输出答案
    return 0;
}