题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi

· · 题解

双指针策略：使用两个指针 i 和 j 。i 从数组开头开始，指向当前尝试的较小麻糬；j 从数组开头开始，寻找能放在 A_i 上的大麻糬。

条件判断：在 while 循环中，j 指针会向右移动，直到找到第一个能够叠放在 A_i 上的麻糬，即满足条件 A_j \ge 2 \times A_i 。如果找到这样的 j ，则增加可以制作的 K 的数量，并移动两个指针，否则停止循环。

输出结果：最后输出计算得到的 K 。

时间复杂度 该算法的时间复杂度为 O(N) ，因为每个指针最多遍历一遍数组。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,i,j,k,a[500001];
// i 指向0小的麻糬
// j 指向大的麻糬
// k 可以制作的 kagamimochi 的数量
signed main(){
    cin >> n;
    for(int i=0;i<n;i++)cin >> a[i];
    // 使用双指针法来寻找可叠放的麻糬
    while(i<n/2 && j<n){// i 最多走到 N/2，j 从前往后遍历
        // 寻找第一个大于等于 A[i] * 2 的元素 A[j]
        while(j<n && a[j]<2*a[i])j++;
        if(j<n){// 找到这样的 A[j]，可以叠放
            k++;// 增加可以制作的 kagamimochi 数量
            i++;// 继续下一对
            j++;// 也要移动到下一个大麻糬
        } 
        else break; // 没有找到合适的叠放对象，停止
    }
    cout << k; // 输出最大可制作的 kagamimochi 数量
    return 0;
}