首页 > 其他分享 >E - Simultaneous Kagamimochi (二分答案+贪心)

E - Simultaneous Kagamimochi (二分答案+贪心)

时间:2025-01-12 11:21:39浏览次数:9  
标签:arr 组合 int ll mid Simultaneous ans Kagamimochi 贪心

题目链接:https://atcoder.jp/contests/abc388/tasks/abc388_e

题意:

给定一个数组,当数组中一个数的两倍不超过另一个数时,认为这两个数可以组成一对,(组合后这两个数无法再次进行组合),求最大组合数

思路:

如果能条件能满足k对,一定能满足k-1对。同时尽量让 小的 和 大的里面相对小 的组合

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
const int maxn=5e5+5;
ll arr[maxn];
ll ans;
bool check(int mid)
{
	for(int i=1;i<=mid;i++)
	{
		if(2*arr[i]>arr[n-mid+i])return false;
	}
	return true;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>arr[i];
	int l=0;
	int r=n/2;
	while(l<=r)
	{
		int mid= l+r>>1;
		if(check(mid))
		{
			ans=mid;
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	cout<< ans;
	return 0;
}

标签:arr,组合,int,ll,mid,Simultaneous,ans,Kagamimochi,贪心
From: https://www.cnblogs.com/benscode/p/18666793

相关文章

  • 题解:AT_abc388_g [ABC388G] Simultaneous Kagamimochi 2
    鉴于本题解书写时洛谷题面暂无中文翻译,为避免可能的歧义或困惑,先对本题解中的译法进行约定:(顺便吐槽音译怪)英文题面中“mochi”或日文题面中“餅”译为“饼”。英文题面中“kagamimochi”或日文题面中“鏡餅”译为“镜饼”。鉴于本题是C和E的加强版,而我懒得去写那两题的题......
  • 【机器人学和计算机视觉】SLAM(Simultaneous Localization and Mapping)原理与技术实现
    引言SLAM(SimultaneousLocalizationandMapping,即时定位与地图构建)是机器人学和计算机视觉领域的一项关键技术。它允许机器人在未知环境中自主导航,同时构建环境的地图并确定自身的精确位置。SLAM技术在机器人、无人驾驶、增强现实和无人机等领域有着广泛的应用。本文将......
  • 常见的七种贪心算法应用实例
            贪心算法(GreedyAlgorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。以下是一些常见的贪心算法应用实例:1.钱币找零问题:        在找零时,希望用最少数量的钱币凑成特定的金额。......
  • 代码随想录算法训练营第二十八天-贪心算法-122. 买卖股票的最佳时机II
    有奇妙的解法分析要获得利润,就是当天卖出前一天买入的的利润,也就是当天价格减去前一天的价格通过这样的运算,可以得到一个新的序列,这个序列就是上一道53的最大子序和的应用了而且把这些子序和中所有正数值都加到一起就是最大利润了#include<iostream>#include<vector>c......
  • 划分字母区间(贪心算法)
    给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。 示例1:输入:s="ababcbacadefegdehijhklij"输出:[9,7,8]......
  • 5.贪心
    贪心开题顺序:\(IHCJEBA\)\(A\)[AGC032E]ModuloPairing若没有\(\bmodm\)的限制,将\(\{a\}\)升序排序后取第\(i\)大和第\(i\)小进行匹配,调整法即可证明。以\(a\leb\lec\led\)为例,由\(\begin{cases}a+c\leb+c\leb+d\\a+d\leb+d\end{cases}\)......
  • 跳跃游戏II(贪心算法)
    给定一个长度为 n 的 0索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i+j] 处:0<=j<=nums[i] i+j<n返回到达 nums[n-1] 的最小跳跃次数。生......
  • 跳跃游戏(贪心算法)
    给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1:输入:nums=[2,3,1,1,4]输出:true解释:可以先跳1步,从下标0到达下标......
  • 买卖股票的最佳时机(贪心算法)
    给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任......
  • Luogu P9646 SNCPC2019 Paper-cutting 题解 [ 紫 ] [ manacher ] [ 贪心 ] [ 哈希 ] [
    Paper-cutting:思维很好,但代码很构式的manacher题。蒟蒻2025年切的第一道题,是个紫,并且基本独立想出的,特此纪念。判断能否折叠我们先考虑一部分能折叠需要满足什么条件。显然,这一部分需要是一个长度为偶数的回文串。那么横向和纵向会不会影响呢?答案是不会,因为横向折了之后,折......