首页 > 代码库 > -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;
}