专栏文章

题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi

lljk8886
AT_abc388_e题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqjarju
此快照首次捕获于
2025/12/04 05:43
3 个月前
此快照最后确认于
2025/12/04 05:43
3 个月前
查看原文

题目分析

考虑双指针。
这道题肯定不能贪心，因为无论是从前面开始找配对，还是从后面开始找，都不能让答案最大。比如 1 1 2 2 4 4 中，无论是从前面开始找，还是从后面开始找，都只能配出两对，但答案是三对。所以，我们先排序，在把麻薯分成两段，前面一半一段，后面一半一段，这样就可以解决前面的问题了。注意到 ai≤ai+1(1≤i<n)a_i \le a_{i+1} (1 \le i < n)，所以不用排序了。时间复杂度 O(n)O(n)。

代码

CPP
#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
inline ll read()
{
	ll res = 0, f = 1;
	char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 5e5 + 5;
int n = read(), a[N], ans; 
int main()
{
	for (int i = 1; i <= n; i++) a[i] = read();
	int l = 1, r = n / 2 + 1; // 从一半开始 
	while (l <= n / 2 && r <= n)
	{
		if (a[l] * 2 <= a[r]) l++, ans++; // 满足条件 
		r++;
	}
	write(ans);
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...