题解：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)

，因为每个指针最多遍历一遍数组。

CPP

#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;
}

题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi

文章操作

相关推荐

评论

题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi