首页 > 代码库 > 六月十九日测试 五颜六色的小动物
六月十九日测试 五颜六色的小动物
题目描述
1.题目描述：
小东东上小学了， 作为奖品东东爸送给小东东一些小动物。
每个小动物都有一个固定的颜色和大小。
小东东在给小动物们一个编号后发现：第i个小动物的颜色是i，大小是Ai。
每个小动物i可以吸收大小不超过是它两倍的另一个小动物。 当颜色是x、大小是Ax的小动物x溶解颜色是y和大小是Ay的小动物y时（ Ay≤2*Ax） ，
它们会变成一个颜色是x，大小是Ax +
Ay小动物。
注：由于小动物大小的原因，它们相互都有可能吸收对方。
很显然最后只会剩一个小动物。
现在小东东想知道，
最后剩下的一个小动物可能的颜色种数。
2.输入：
第一行一个整数N表示有多少小动物。
第二行包含N个整数，每个整数Ai表示第i个小动物的大小。
3.输出：
一个整数，表示最后剩下的一个小动物可能的颜色种数。
4.样例：
1. 输入1：
3
3 1 4
2. 输出1：
2
3. 样例解释：
可能的颜色是1， 3。
一种可能：第三个小动物溶解第二个小动物，之后第一个小
动物溶解了第三个小动物，最后剩下的小动物颜色是1。
4.
输入2：
5
1 1 1 1 1
5. 输入2：
5
6.
样例解释：
最后每个小动物都有可能剩下
5.数据范围：
2≤N≤100000
1≤Ai≤109
这道题可以说是一道贪心的题目，我们将数据排序就会发现，最大的一定可以留下
第二大的可以吃掉所有他前面的，如果他吃掉了所有他前面的大小*2>=最大的，它也可以留下
同理一直向前判断，知道有一个a[i]吃掉它前面所有的和*2<a[i+1]，则他及他前面的都不可能留下。
下面是我写的代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll sum1[100001]={0},a[100001]; int main() { ll i,j; ll n; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } if(n==1) { cout<<"1"; return 0; } sort(a,a+n+1); for(i=1;i<=n;i++) { sum1[i]=sum1[i-1]+a[i]; } ll count=1; ll step,step1=0; if(sum1[n-1]*2>=a[n]) { count++; step=1; } else step=0; if(step!=0) { for(i=n-2;i>=1;i--) { if(sum1[i]*2>=a[i+1]) { count++; } else break; } } printf("%lld",count); }
六月十九日测试 五颜六色的小动物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。