首页 > ACM题库 > HDU-杭电 > HDU 4038-Stone-贪心-[解题报告]HOJ
2015
04-16

HDU 4038-Stone-贪心-[解题报告]HOJ

Stone

问题描述 :

Given an array of integers {xi}. Each time you can apply one of the following operations to the array:
1. Choose an integer x from the array, replace it with x+1.
2. Add a new integer 1 to the array.

Define p as the product of all integers in the set. i.e. p=x1*x2*x3*…
What’s the maximum possible value of p after exactly M operations?

输入:

First line is a integer T (T ≤ 100), the number of test cases.
The first line of each test case contains two integers N and M, the number of integers in the initial set, and the number of operations.
The second line is N integers xi initially in the set.
1 ≤ N ≤ 100000
0 ≤ M ≤ 10^18
-10000 ≤ xi ≤ 10000

输出:

First line is a integer T (T ≤ 100), the number of test cases.
The first line of each test case contains two integers N and M, the number of integers in the initial set, and the number of operations.
The second line is N integers xi initially in the set.
1 ≤ N ≤ 100000
0 ≤ M ≤ 10^18
-10000 ≤ xi ≤ 10000

样例输入:

4
1 1
5
3 2
1 2 3
3 2
-1 2 3
3 1
-3 -3 -3

样例输出:

Case 1: 6
Case 2: 18
Case 3: 6
Case 4: -18

题意:

        给一个数列,可以对这数列进行两种操作:A.使其中的一个数加1;B.增加1到这个数列。要求这个数列的乘积最大。

思路:贪心+模拟。

我觉得不够清晰。再理一遍。

     1. 负数个数为奇数的时候我们把最大的负数变成0;

     2.0是我们在这题当中很讨厌的东西(其他题也有卡0的,比如0!= 1,1对1的逆元是0),所以我们先将所有的精力集中对付0。

     3.当0没有了的时候,我们其次讨厌1。为什么呢,因为1->2是2倍的收益,相对其他的数以及其他的添加1的操作来说,她用1的收益最大。我们要得到最大收益,所以,把1全部变成2。

     4.没有1,0的时候,我们把2全部变成3。是3/2的收益。

     5.没有2,1,0的时候,我们是不是要把所有的3变成4呢?不是的。为什么这里就不是,上面就是呢?是这样的。当操作m=2时,我们用这两个二将两个1变成2收益是4 > 2,将两个2变成3收益是1.5*1.5 > 2,将两个3变成4的收益是1.333333*1.333333 = 1.777777 < 2,还不如将这两个一加在一起变成2加到原来的序列里面;当m=3时,我们用这3个二将3个1变成2收益是8 > 3,将3个2变成3收益是1.5*1.5
*1.5 > 3,将两个3变成4的收益是1.333333*1.333333 * 1.333333 < 3;以此类推。

     6.由以上推得,做完以上操作之后如果m = 1,则加到最小的那个非负数上;m>1时,如果m%3==0,则加m / 3个3就行;(m – 1) % 3 == 0时,加(m-1)/3 – 1个3,再加个4;(m – 2) % 3 == 0,加(m – 2)/3个3,再加个2。

到此,终于完了。。。。

做题过程:

       将思路理清楚之后就容易了,调了一会,1A。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define mod 1000000007
using namespace std;
int t,n,a[100010],odd_num,m,indx,Minpos,Min;
__int64 ans;
void init(){
    odd_num = 0;    ans = 1;
    Min = mod;  indx = 1;//初始化!!!
}
long long pow_mod(int a,int n,int p)
{
    long long ret=1;
    long long A=a;
    while(n)
    {
        if (n & 1)
            ret=(ret*A)%p;
        A=(A*A)%p;
        n>>=1;
    }
    return ret;
}
int main()
{
    scanf("%d",&t);
    for(int ca = 1; ca <= t; ca ++){
        scanf("%d%d",&n,&m); init();
        for(int i = 1; i <= n;i ++){
            scanf("%d",a + i);
            if(a[i] < 0) odd_num++;
        }
        sort(a + 1, a + 1 + n);
        if(odd_num & 1){//负数个数为奇数的时候,去改最大的负数
            int j = 1;
            while(a[j] < 0) j ++;   indx = -- j;//
//            cout << "j" << j << endl;
            if(a[j] + m > 0) m += a[j], a[j] = 0;
            else a[j] += m,m = 0;
        }
        if(m > 0){
//            for(int j = 1; j <= n - 1; j ++)
//                printf("%d ",a[j]);  printf("%d\n",a[n]);
//            cout << indx << endl;
            for(int j = indx; j <= n && m > 0; j ++)
                if(a[j] == 0) a[j] ++, m --;
            for(int j = indx; j <= n && m > 0; j ++)
                if(a[j] == 1) a[j] ++, m --;
            for(int j = indx; j <= n && m > 0; j ++)
                if(a[j] == 2) a[j] ++, m --;

//            for(int j = 1; j <= n - 1; j ++)
//                printf("%d ",a[j]);  printf("%d\n",a[n]);

            for(int j = 1; j <= n; j ++)
                ans = (ans * a[j]) % mod;
            if(m <= 0){
                printf("Case %d: %I64d\n",ca,ans);
            }else{
                if(m == 1){
                    for(int j = 1; j <= n; j ++)
                        if(Min > a[j]) Min = a[j], Minpos = j;
                    ans /= a[Minpos];
                    ans = (ans * (a[Minpos] + 1)) % mod;
                    printf("Case %d: %I64d\n",ca,ans);
                }else if(m % 3 == 0){
                    ans = (ans * pow_mod(3,m/3,mod)) % mod;
                    printf("Case %d: %I64d\n",ca,ans);
                }else if((m - 1) % 3 == 0){
                    ans = (ans * pow_mod(3,(m - 1)/3 - 1,mod)) % mod;
                    ans = (ans * 4) % mod;
                    printf("Case %d: %I64d\n",ca,ans);
                }else if((m - 2) % 3 == 0){
                    ans = (ans * pow_mod(3,(m - 2)/3,mod)) % mod;
                    ans = (ans * 2) % mod;
                    printf("Case %d: %I64d\n",ca,ans);
                }
            }
        }
        else{
            for(int j = 1; j <= n; j ++)
                ans = (ans * a[j]) % mod;
            printf("Case %d: %I64d\n",ca,ans);
        }
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/julyana_lin/article/details/7920010


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。