首页 > 代码库 > Problem G 宝石合成 (内蒙古14年省赛)

Problem G 宝石合成 (内蒙古14年省赛)



1117: Problem G 宝石合成

时间限制: 1 Sec  内存限制: 128 MB
提交: 18  解决: 4
[提交][状态][讨论版]

题目描述

故事人物:豆豆强   走上致富之路的豆豆强越来越有土豪范,买房买车已经提不起他的兴趣,现在玩起了魔法宝石。   这种宝石分为不同品质等级,并且3个品质等级为 i 的宝石,可以合成一个品质等级为 i+1 的宝石。更加神奇的是,不管这个宝石的品质怎么变,一个宝石永远只占一个单位的空间。   现在豆豆强需要买一个全金打造的保险柜来储存这些宝石。本来对于他这种土豪来说,这个一点问题都没有。可是全金的保险柜太重,所以他希望把宝石的体积缩减到最小。在这之前,豆豆强想请你帮他计算一下,这些宝石至少需要多少单位的空间来存储。

输入

第一行有一个正整数T,表示豆豆强要买T次宝石。   接下来 T 次购买,每次购买首先是一个n,表示豆豆强这次要买的宝石种类数。接下n行,每行有两个数a,b, 分别表示宝石的品质和已经买的数量。      限制条件:   1 <= n <= 10000   1 <= a <= 10000   1 <= b <= 10000

输出

对于每次购买,请首先输出一行Case #t:,其中,t表示这是第几次购买。   紧接着一行输出这次购买的宝石至少要占的空间。

样例输入

3
1
111 9
2
111 6
112 1
3
111 3
112 2
113 2

样例输出

Case #1:
1
Case #2:
1
Case #3:
1

内蒙古省赛题,开始做这道题的时候,范围取的小了,导致一直wa,题目给的是10000,开始就等于10000导致一直wa,后来把范围改大就a了,在比赛的时候还是要注意范围问题,这些细节的地方还是要处理好;

这题的基本思路也比较简单,直接进行合并,暴力就可以过了;
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=10500;
int q[maxn];
int main()
{
    int t,n,a,b,i,pos,count,k=1;
    scanf("%d",&t);
    while(t--)
    {
        count=0;
        memset(q,0,sizeof(q));
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
           scanf("%d%d",&a,&b);
           q[a]+=b;//先前这里忘记+号了,wa了
        }
        for(i=1;i<=maxn;i++)
        {
            q[i+1]=q[i+1]+q[i]/3;//这种合并的方式还算是比较巧妙
            q[i]=q[i]%3;
            pos=i+1;
            while(q[pos]>=3)
            {
                q[pos+1]=q[pos+1]+q[pos]/3;
                q[pos]=q[pos]%3;
                pos++;
            }
            if(q[i]!=0)
             count+=q[i];
        }
        printf("Case #%d:\n%d\n",k++,count);
    }
    return 0;
}


Problem G 宝石合成 (内蒙古14年省赛)