TOJ 3800: -3+1

痛定思痛。 2022-05-06 10:56 95阅读 0赞

## **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.

1.  Choose any element in the sequence, say x(satisfying x ≥ 3), and subtract 3 from x.
2.  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);
    	}
    }

[ZOJ 10th Anniversary]: http://210.32.82.1/acmhome/search.do?method=simpleSearch&searchFrom=Source&queryString=ZOJ+10th+Anniversary