首页 > 其他分享 >【题解】AT_agc011_b [AGC011B] Colorful Creatures

【题解】AT_agc011_b [AGC011B] Colorful Creatures

时间:2024-11-21 20:31:44浏览次数:1  
标签:agc011 int 题解 AGC011B 生物 最后 排序 吸收

原题传送门


我们知道,要想使一个生物能活到最后,那么它进行的每一次吸收前,它的大小应当尽可能大,所以我们考虑贪心,对生物的大小从小到大排序,每个生物都从小的开始吸收,看能不能活到最后,时间复杂度 \(\mathcal{O(n^2)}\)。

我们还知道,排序后,生物 \(i\) 能活到最后,则生物 \(i+1\sim n\) 一定也能活到最后;生物 \(i\) 不能活到最后,则生物 \(1\sim i-1\) 一定也不能活到最后。所以我们可以在排序后从后往前扫描 \(a_i\),用前缀和求得 \(a_i\) 当前最大的大小(即吸收前面所有比它小的),判断能否吸收生物 \(i+1\),吸收不了则它就或不到最后,比它小的生物也或不到最后,所以终止扫描。时间复杂度降为 \(O(n)\)。

\(\texttt{code}\)

/*Written by smx*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define QAQ cout<<"QAQ\n";
const int MAXN=1e5+5,inf=1e18,mod=1e9+7;
int n,ans=1;
int a[MAXN],sum[MAXN];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=n-1;i>=1;i--){
		if(sum[i]*2>=a[i+1]){
			ans++;
		}else{
			break;
		}
	}
	cout<<ans;
	return 0;
}

标签:agc011,int,题解,AGC011B,生物,最后,排序,吸收
From: https://www.cnblogs.com/shimingxin1007/p/18561463

相关文章

  • P7906 [Ynoi2005] rpxleqxq 题解
    P7906[Ynoi2005]rpxleqxq题解题目大意给定一个长度为\(n\)的序列\(A\),和一个常数\(k\)。有\(m\)次询问,每次给定一个区间\([l,r]\),询问有多少二元组\((i,j)\),满足:\(1\leqi<j\leqn\);\((A_i\oplusA_j)\leqk\)。Solve前置知识:莫队二次离线。对于普通莫队,端......
  • [CSP-S2019]Emiya 家今天的饭 题解
    题意分析给出一个矩阵,要求每行只能选一个节点,每列选的节点不能超过所有选的节点的一半,不能不选,给出每个节点的选择方案数,求总方案数考场思路考虑暴力枚举每一个点的选择情况,最后统计答案。对于行:但是因为有每一行只能选择一个的限制,所以考虑当前行选择一个后直接转跳到下一行......
  • [NOIP2016 提高组] 蚯蚓 题解
    考场思路考虑要动态维护最大值,可以直接使用优先队列进行维护,但是,考虑到我们并不好直接修改优先队列中的每一个元素,所以决定使用vector先排一遍序,再使用冒泡排序进行动态维护,时间复杂度\(O(mn)\),可以拿35pts。代码#include<iostream>#include<vector>#include<algorithm>......
  • C语言 蓝桥杯某例题解决方案(查找完数)
    蓝桥杯原题: 一个数如果恰好等于它的因子之和,这个数就称为“完数”。例如6=1+2+3.编程找出1000以内的所有完数。这个题没有很大的难点,与我们上一个解决的问题“质因数分解”不同,它不需要判断因数是否是质数,因此我们的工作量会小很多。现在我们的想法还是类似,首先找到......
  • 【Flinkcdc问题解决】java.lang.NoClassDefFoundError: org/apache/flink/shaded/guav
    1.环境介绍Flink1.17+Flinkcdc2.2.12.问题描述使用Flink1.17和Flinkcdc2.2.1环境进行数据加工,但是报以上错误,原因是版本不匹配,flinkcdc2.2.1用的是guava18,但是flink1.17用的是guava30,导致冲突。3.问题解决添加flink-sql-connector-mysql-cdc依赖<dependen......
  • [题解](更新中)2024/11/21 模拟赛 / 2023牛客OI赛前集训营-提高组(第二场) A~B
    整套都是原题所以就不设密码了(原题页面:https://ac.nowcoder.com/acm/contest/65193题解:https://www.nowcoder.com/discuss/540225827162583040\(60+30+20+20=130\)。每日挂分之T2线段树不开\(4\)倍+\(10^6\)数量级输入不关同步流,\(\bf\colorbox{MidnightBlue}{\texttt{\color{......
  • ABC379 题解[A-D]
    ABC379题解目录ABC379题解目录A CyclicB StrawberriesC SowingStonesD HomeGardenE SumofAllSubstringsA Cyclicmanwhatcanisay?#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingull=unsignedlonglong;usingld=l......
  • 去水印小程序downloadFile域名问题解决方式
    ......
  • Atcoder Regular Contest 060 题解
    ARC060C.TakandCards*1583简单题。考虑一个非常非常常见的Trick。把区间平均值为\(k\)转化为区间和为\(0\)只需要将每个数都减去\(k\)即可。然后就是一个朴素的背包求和为\(0\)方案数。注意处理负数下标就好了。#include<bits/stdc++.h>usingnamespacestd;typ......
  • 【题解】洛谷P3531: [POI2012] LIT-Letters
    P3531[POI2012]LIT-Letters写了个假做法有点伤心,本以为是两个都求逆序对然后答案相减,但是这样在部分数据上确实合法,但是实际上毫无章法没有逻辑。正解考虑贪心,我们一个数字肯定要找最前面,第二次出现就去最前面第二次出现的位置,因为如果第一个A放在了后面,那么就有可能产生更对......