首页 > 代码库 > -3+1
-3+1
题目详情
有一个数列,所有的数都是非负整数,你可以进行如下方式进行一次操作(注意一次完整的操作必须先后完成如下两个步骤):
(1) 任选一个不小于3的数,把它减少3。
(2) 任选一个数把它增加1。
请问,最多能够操作多少次?
输入格式:
多组数据,每组数据第一行是一个正整数n,表示数列中数的个数。(1<=n<=20000)
第二行包含n个空格分隔的非负整数,每个整数不超过1000000。
输出格式:
对每组数据输出一行,表示最多可以进行的操作次数。
输入样例:
1
10
2
10 11
输出样例:
4
10
解题思路
对于每一个数x:用sum来记下可加的数x/3,用一个数组保存每个数%3之后的余数(即0,1,2)的个数。
则要求的是将每在sum里面-3一次,则可以在0,1,2中+1一次的最多操作次数。
利用贪心的思想,先把全部的2操作完之后,再把全部的1的操作完,最后考虑0的情况。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; typedef long long ll; ll sum,a[3]; int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); ll n; while(~scanf("%lld",&n)) { sum=0; ll res=0; a[1]=a[2]=0; for(int i=0; i<n; i++) { ll x; scanf("%lld",&x); sum+=x/3; x%=3; a[x]++; //统计 } res=sum; if(sum>0) res+=a[2]; while(1)//1 { ll tmp=min(sum>>1,a[1]); res+=tmp; sum-=tmp; a[1]-=tmp; if(sum<1||a[1]<1) break; } while(1)//0 { ll tmp=sum/3; sum%=3; sum+=tmp; res+=tmp; if(sum<=2) break; } printf("%lld\n",res); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。