题目:
思路:
本题注意题目的条件即可,题意说一个摩天轮可以坐一个人或者两个人,那么显然我们就可以贪心一下
具体的,我们可以让最小的去匹配最大的,如果此时大于 x,那么显然我们根本无法使得 最大的那个存在两个人共坐一个摩天轮的方案,因此最大的那个就肯定要单独坐一辆,那么此时就看看次大的能不能和最小的匹配,以此类推,当能匹配时就直接跳出匹配过程即可,然后对次小值进行上诉操作即可
对于上诉过程,不难发现双指针即可(代码中的 solve 为另类写法,忽视即可,主要在 solve2)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());void solve2()
{int n,x;cin >> n >> x;vector<int> a(n);for (int i = 0; i < n; i++){cin >> a[i];}sort(a.begin(),a.end());int l = 0,r = n-1;int ans = 0;while (l <= r){while(r > l && a[l] + a[r] > x){r--;ans++;}l++,r--;ans++;}cout << ans << endl;
}void solve()
{int n, x, p;cin >> n >> x;multiset<int> mst;for (int i = 0; i < n; i++){cin >> p;mst.insert(p);}int ans = 0;while (!mst.empty()){if (*mst.begin() * 2 <= x){auto it = mst.upper_bound(x - *mst.begin());if (it != mst.begin()){it--;if (it != mst.begin()){mst.erase(it);}}}ans++;mst.erase(mst.begin());}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--){solve2();}return 0;
}