TOJ 3800: -3+1-蒲公英云

TOJ 3800: -3+1

3800: -3+1

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte
总提交: 150 测试通过:59

描述

ZOJ is 10 years old! For celebrating, we are offering the easiest problem in the world to you.

Recently we received a long sequence. We can modify the sequence once by the following two steps.

Choose any element in the sequence, say x(satisfying x ≥ 3), and subtract 3 from x.
Choose any element in the sequence, say x, and add 1 to x.

Now, we want to know how many times at most the sequence can be modified.

输入

The input contains multiple test cases. For each case, the first line contains an integer n(1 ≤ n ≤ 20000). The second line contains n integers describing the sequence. All the numbers in the sequence are non-negative and not greater than 1000000.

输出

Output number of times at most the sequence can be modified, one line per case.

样例输入

1
10
2
10 11

样例输出

4
10

题目来源

ZOJ 10th Anniversary

题意：有一个操作，先对序列中任意一个数字-3，然后再对任意一个数字+1，问最多可以进行几次这样的操作。

思路：输入的时候，就把每个数字处理一下，能/3的都除，记录除了几次即为现有+1的次数，然后这个数就变成了%3，所以整个序列就变成0,1,2的序列（op用来记录0,1,2分别的个数）。

然后先考虑2，因为给2一个1，它变成3之后又能+1，所以对2而言，操作数++，1的次数不变，但前提是1至少有一次。

然后考虑1，因为让1变成3要2个1，但是1变成3之后又能+1，所以容易理解为1个1就能转换1，所以要先判sum1为2的情况，这个时候只能处理到一个1，如果有多的话，就算作1个+1处理一个1。

考虑完以上，整个序列全部为0，此时剩下1的个数去填满，要循环的填，因为填完一个又会增加1次。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
int a[20010],op[5];
int main() 
{    
    int n,i,j,cs,sum1;
    while(scanf("%d",&n)!=EOF)
    {
        memset(op,0,sizeof op);
        cs=0;sum1=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            cs+=a[i]/3;
            sum1+=a[i]/3;
            a[i]=a[i]%3;
            op[a[i]]++;
        }
        if(sum1)
        cs+=op[2],op[2]=0;
        if(sum1==2)
        cs++,op[1]=0,sum1=0;
        else if(sum1>=op[1])
        cs+=op[1],sum1-=op[1],op[1]=0;
        while(sum1>=3)
        {
            cs+=sum1/3;
            sum1=sum1/3+sum1%3;
        }
        printf("%d\n",cs);
    }
}