题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi

ljk8886 · 2025-01-12 10:32:19 · 题解

题目分析

考虑双指针。

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

代码

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