贪心法（四）：HDU题库中的贪心法应用例题

        下面我们通过解决HDU题库中的几道应用贪心法思想编写程序的例题，进一步体会贪心法的应用。

【例1】卡片游戏。

问题描述

小明最近宅在家里无聊，于是他发明了一种有趣的游戏，游戏道具是N张叠在一起的卡片，每张卡片上都有一个数字，数字的范围是0~9，游戏规则如下：

首先取最上方的卡片放到桌子上，然后每次取最上方的卡片，放到桌子上已有卡片序列的最右边或者最左边。当N张卡片全部都放到桌子上后，桌子上的N张卡片构成了一个数。这个数不能有前导0，也就是说最左边的卡片上的数字不能是0。游戏的目标是使这个数最小。

现在你的任务是帮小明写段程序，求出这个最小数。

输入

第一行是一个数T（T<=1000），表示有T组测试数据；

然后下面有T行， 每行是一个只含有0~9的字符串，表示N（1 <= N <= 100）张叠在一起的卡片，最左边的数字表示最上方的卡片。

输出

对于每组测试数据，请在一行内输出能得到的最小数。

输入样例

565

9876543210

9876105432

输出样例

556

1234567890

1678905432

        （1）编程思路。

        贪心的策略是：数字越小的越应该放在最前面。由于放在最前的数字不能是0，因此需要先遍历整个字符串，找最靠后的最小的非0数字，记录其下标位置pos，以保证其放在第一位。

        由于游戏时，依次取出的每张卡片可以放在桌子上已有卡片序列的最右边或者最左边，因此可以定义一个字符串dest[210]（长度为源串的2倍），然后从中间位置开始放数字，定义两个变量left和right分别表示放每张卡片的左端或右端的位置，初始值均为101（中间位置），将第1个数src[0]放在最左端，即dest[--left]=src[0]。之后从src[1]开始遍历源字符串，对于串中的每个字符src[i]，进行如下处理：

        1）若下标i小于pos，即还没有访问到最靠后的最小的非0数字。则与最左端的数字进行比较，大就放到最右端（后面），小就放到最左端（前面）。

        2）若下标i等于pos，则将其放在最左端，保证最小的非0数字放在第一位。

        3）下标大于pos的字符就只能依次放在最右端了。

      （2）源程序。

#include

int main()

{

    int t;

    scanf("%d",&t);

    while (t--){

        char src[101],dest[210];

        int i;

        scanf("%s",src);

        char min='9';

        int pos=101;

        for (i=0;src[i]!='\0';i++){

            if (src[i]!='0' && min>=src[i]){

                min=src[i];   pos=i;

            }

        }

        int left=101;

        int right=101;

        dest[--left]=src[0];

        for (i=1;src[i]!='\0';i++){

            if (i

                if (src[i]>dest[left]){

                   dest[right++]=src[i];

                }

                else

                   dest[--left]=src[i];

            }

            else if (i==pos)

                dest[--left]=src[i];

            else

                dest[right++]=src[i];

        }

        for (i=left;i

           printf("%c",dest[i]);

        printf("\n");

    }

    return 0;

}

        注：将此源程序提交给HDU4550卡片游戏（http://acm.hdu.edu.cn/showproblem.php?pid=4550）可以Accepted。 

【例2】去掉m个数字。

问题描述

给定一个最多1000位的整数n，从整数n中任意拿掉m个数字后，n最小为多少？

输入

输入包括多个测试用例。

每个测试用例将包含一个给定的整数（最多可能包含1000个数字）和整数m（如果整数包含n个数字，m将不大于n）。给定的整数不包含前导零。

输出

对于每组测试数据，请在一行内输出能得到的最小数，最小数的前导0需去掉。

输入样例

178543 4

1000001 1

100001 2

12345 2

54321 2

输出样例

13

123

321

        （1）编程思路。

        n位的整数去掉m位后会留下n-m位，因此贪心的策略是进行n-m次挑选，每次在剩下的可挑选的数字中找出最小的数字留下来即可。

        设给定的整数保存在字符串s中，s[0]保存最高位，s[n-1]保存最低位。

        第1个数字一定在会在s[0]~s[m]中选一个最小的，因为后面至少得留n-m-1个数字供后面进行选择。若有多个最小的，则选取下标值最小的位置的数字，并标记其位置pos1。将所选取的最小的数字作为结果的第一位（最高位）进行保存。

        第2个数字在s[pos1]~s[m+1]中进行选择，同样后面至少得留n-m-2个数字供以后进行选择。在s[pos1]~s[m+1]中选择最小的数字时，若有多个最小的，则选取下标值最小的位置的数字，并标记其位置pos2。将所选取的最小的数字作为结果的第2位进行保存。

        依次类推，第3个数字在s[pos2]~s[m+2]中进行选择，……，直到完成n-m次选择。

        （2）源程序。

#include

#include

int main()

{

    char s[1005],ans[1005];

    int ok[1005];

    while(~scanf("%s",s)){

        int len=strlen(s);

        int m;

        scanf("%d",&m);

        int w=0;

        memset(ok,1,sizeof(ok));

        int i,k;

        for (i=m;i

        {

            char minn=s[i];

            int pos=i;

            for (k=i-1;k>=0;k--)

            {

               if (ok[k]==0)

                  break;

               if (s[k]<=minn)

               {

                  minn=s[k];

                  pos=k;

               }

            }

            ok[pos]=0;

            ans[w++]=minn;

        }

        int flag=0;

        for (i=0;i

        {

           if (flag==0 && ans[i]=='0')

              continue;

           printf("%c",ans[i]);

           flag=1;

        }

        if(flag==0) printf("0");

        printf("\n");

    }

    return 0;

}

        注：将此源程序提交给HDU 3183 A Magic Lamp（http://acm.hdu.edu.cn/showproblem.php?pid=3183）可以Accepted。

 【例3】最小系数和。

问题描述

设有如下的等式：a0+a1*21+a2*22+...+am*2m=n。给定整数n和m，问等式成立时，各系数和a+a1+…+am的最小值为多少？

输入

有多个测试用例。输入的第一行包含一个整数T（1≤T≤105），表示测试用例的数量。

对于每个测试用例：包含两个整数n和m（0≤n、 m≤109).

输出

对于每个测试用例，输出各系数和a+a1+…+am的最小值。

输入样例

10

1 2

3 2

5 2

10 2

10 3

10 4

13 5

20 4

11 11

12 3

输出样例

         （1）编程思路。

        因为n的范围为109，所以m最大到31就够了，因为231已经超过了109。因此当m超过31时，系数a32~am均为0。

        贪心策略是：由于1*24=2*23，即a4=1和a3=2等价，因此应尽可能用2的高次方来表示n。即从系数am开始考虑，n中尽可能减掉足够的2m，之后减去足够多的2m-1，直到n减为0。

       （2）源程序。

#include

int power(int x,int n)

{

    int p=1,i;

    for (i=1;i<=n;i++)

        p*=x;

    return p;

}

int main()

{

    int t;

    scanf("%d",&t);

    while (t--){

        int n,m,sum,i;

        scanf("%d%d",&n,&m);

        if (m>31) m=31;

        sum=0;

        for (i=m;i>=0;--i){

            int cnt=power(2,i);

            sum+=n/cnt;

            if (n%cnt==0) break;

            n%=cnt;

        }

        printf("%d\n",sum);

    }

    return 0;

}

        注：将此源程序提交给HDU5747 Aaronson（http://acm.hdu.edu.cn/showproblem.php?pid=5747）可以Accepted。 

【例4】不进位加法。

问题描述

给出两个长度不超过 106 的数字串，将这两个数字串各自打乱后随机组合，但是打乱重组后不能有前导0。然后将这两个数字串相加，相加的规则是每一位相加，但不进位。例如，计算4567+5789时，结果为9246，计算1234+9876，结果将为0。

问能够得到最大的结果串是多少?

输入

第1行有一个数字T（T<=25），表示测试用例的数量。

对于每个测试用例，有两行：第一行是数字A，第二行是数字B。

A和B的位数相同，且无前导零。

输出

对于测试用例X，首先输出“case #X:”，然后输出不带前导零的最大可能和。

输入样例

5958

3036

输出样例

Case #1: 8984

        （1）编程思路。

        贪心策略是：从高位到低位，每次贪心选择相加起来最大的数字。

        在贪心的过程中，不去枚举加数和被加数，只枚举结果。先分别保存两个数字串中，数字0~9各自出现的次数。由于加法不进位，因此最大可能和的位数应与数字串的位数相同。因此，最大可能和这一结果从高位到低位，依次看能否用两个数字串的数字组成9，不能再看能否组成8，之后是7，…。

最高位要单独处理，因为最高位要求被加数和加数都不能为0。

        （2）源程序。

#include

#include

#define MAXN 1000005

char str1[MAXN],str2[MAXN];

int ans[MAXN];

int main()

{

    int t;

    int iCase = 0;

    scanf("%d",&t);

    while (t--)

    {

        iCase++;

        scanf("%s%s",str1,str2);

        int n = strlen(str1);

        if (n == 1)

        {

            printf("Case #%d: %d\n",iCase,(str1[0]-'0'+str2[0]-'0')%10);

            continue;

        }

        int a[10],b[10];    // a[i]（或b[i])保存加数A（或B）中数字i的个数

        memset(a,0,sizeof(a));

        memset(b,0,sizeof(b));

        int i,j,k;

        for (i = 0;i < n;i++)

        {

            a[str1[i]-'0']++;

            b[str2[i]-'0']++;

        }

        // 首位不能为前导0，因此特别处理

        int x =0, y=0;

        int ttt = -1;

        for (i = 1;i <= 9;i++)

            for (j = 1;j <= 9;j++)

                if (a[i]!=0 && b[j]!=0 && ((i+j)%10) > ttt)

                {

                    x = i;

                    y = j;

                    ttt = (x+y)%10;

                }

        a[x]--;

        b[y]--;

        int cnt = 0;

        ans[cnt++] = (x+y)%10;

        int digit;

        for (digit=9;digit>=0;digit--)

        {

            for (i=0;i<=9;i++)

                if(a[i]!=0)

                {

                    if (i<=digit)

                    {

                        j = digit-i;

                        k = a[i]

                        a[i] -= k;

                        b[j] -= k;

                        while (k--)

                            ans[cnt++] = digit;

                    }

                    j = 10 + digit - i;

                    if (j > 9) continue;

                    k = a[i]

                    a[i] -= k;

                    b[j] -= k;

                    while (k--)

                        ans[cnt++] = digit;

                }

        }

        printf("Case #%d: ",iCase);

        for (i=0;i

            if (ans[i]!=0) break;

        for (;i

            printf("%d",ans[i]);

        printf("\n");

    }

    return 0;

}

        注：将此源程序提交给HDU4726 Kia's Calculation（http://acm.hdu.edu.cn/showproblem.php?pid=4726）可以Accepted。 

【例5】最大的位或。

问题描述

给定自然数l和r，选取2个整数x,y满足l <= x <= y <= r，使得x|y最大。

其中|表示按位或，即C、 C++、 Java中的|运算。

输入

包含至多10001组测试数据。

第一行有一个正整数，表示数据的组数。

接下来每一行表示一组数据，包含两个整数l,r。

保证 0 <= l <= r <= 1018。

输出

对于每组数据输出一行，表示最大的位或。

输入样例

1 10

0 1

1023 1024

233 322

1000000000000000000 1000000000000000000

输出样例

15

2047

511

1000000000000000000

       （1）编程思路。

        对于或运算“ | ”，满足a | b >= max(a,b)。

       因此，对于给定的自然数l和r，r不需要改变，只需改变l的值。把l和r写成二进制的形式进行分析，可知：

        1）从高位起，找到两个数第一个不相同的位p，对于前面的高位，如果为0，则不能改为1，因为会超出范围；如果为1，则不应改为0，因为其值会变小。

        2）对于找到的第一个不相同的p位，r对应的二进制的p位必为1，l的p位必为0。所以结果的p位取1。

        3）由于在p位时，r为1，l为0，因此即使l在后面的位全部取值为1，都满足l

        4）因此，结果为l和r两个数高位相同的部分 + 后一部分全部取值为1。

      （2）源程序。

#include

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--) {

        long long l, r, ans = 0;

        scanf("%lld%lld",&l,&r);

        long long x = r,t1,t2;

        int d = -1;

        while (x) {          // 求出r对应的二进制数的位数

            d++;

            x >>= 1;

        }

        int i;

        for (i = d; i>=0; i--) {

            t1 = (l>>i)&1;

            t2 = (r>>i)&1;

            if (t1==t2) ans += t1*(1LL<

            else break;

        }

        if (i>=0)  ans += (1LL<<(i+1))-1;

        printf("%lld\n",ans);

     }

     return 0;

}

        注：将此源程序提交给HDU 5969 最大的位或（http://acm.hdu.edu.cn/showproblem.php?pid=5969）可以Accepted。 

【例6】电波。

问题描述

阿里正在做一个物理实验，要求他观察一个电波。他需要进一步研究每个峰值和谷值的高度（峰值表示该值严格大于其相邻值，谷值表示该值严格小于其相邻值）。他确实把这些数字写了下来，但他太粗心了，以至于把它们写在一行中，没有分开，例如“712495”可能代表“7 12 4 9 5”。他能记得的唯一信息是：

1）数据以谷值开始；

2）每个值都是峰值或谷值。

现在他想插入空格以使数据有效。如果存在多个解决方案，他将选择空白较多的解决方案。

输入

输入由几个测试用例组成。

第一行包含一个整数N（1<=N<=100），即数据的长度。

第二行包含一个字符串S，即他记录的数据。S只包含数字。

输出

一个整数，所能插入的最多空格数。

输入样例

712495

输出样例

        （1）编程思路。

        为了尽可能多地插入空格，显然波谷和波峰都用一位数最佳。按照贪心的思想，波谷一定是一位数，波峰一位数不够大的时候加入到两位数就一定够大了的。

        具体处理时，当在寻找波谷碰到零时，零就自然当成波谷；当在寻找波峰碰到零时，将前面的波谷加到前一个波峰上，让当前的零做波谷，使得波谷的值尽量小。

        源程序中，变量a表示前一个值，b表示当前考虑的值，tag为偶数时表示正在寻找波谷，奇数时在寻找波峰。

       （2）源程序。

#include

int main()

{

         int n;

         while (scanf("%d", &n) != EOF)

         {

                   char data[101];

                   scanf("%s", data);

                   int  a, b,tag = 0;

                   a = 11;

                   b = 0;

                   int i,ans = 0;

                   for (i = 0; i < n; i++)

                   {

                            b = (data[i] - '0');

                            if (tag % 2 == 0){    // 确定波谷

                                     if (b < a){

                                               a = b;

                                     }

                                     else {

                                               i++;

                                               a=data[i]-'0';

                                     }

                            }

                            else {               // 确定波峰

                                     if (b > a) {

                                               a = b;

                                     }

                                     else{

                                               if (b == 0){

                                                        while(data[i] == '0'){

                                                                 i++;

                                                                 if (i >= n) break;

                                                        }

                                                        a = 0;            // 0做波谷

                                                        b = data[i]-'0';

                                                        a = b;

                                               }

                                               else{

                                                        i++;

                                                        a = b*10 + (data[i] - '0');

                                               }

                                     }

                            }

                            if (i >= n) break;

                            ans ++;    tag ++;

                   }

                   printf("%d\n", ans-1);

         }

         return 0;

}

        注：将此源程序提交给HDU 4105 Electric wave（http://acm.hdu.edu.cn/showproblem.php?pid=4105）可以Accepted。 

【例7】对子和顺子。

问题描述

给出n个整数a1、a1、…、an，ai（1≤ai≤n）。

两个相同的数字（例如：2和2）可构成一个对子，三个连续的整数（如：2，3，4）可构成一个顺子。

现在请你用给定的这些整数来尽可能多的构成顺子和对子。注意，每个整数只能使用一次。

输入

输入包含几个测试用例。

对于每个测试用例，第一行包含一个整数n（1≤N≤106）。.

然后下一行包含n个空格分隔的整数ai（1≤ai≤n）。

输出

对于每个测试用例，在一行中输出可构成顺子和对子的总数。

输入样例

1 2 3 4 5 6 7

1 1 1 2 2 2 3 3 3

2 2 3 3 3 3

1 2 3 3 4 5

输出样例

        （1）编程思路。

        定义数组int a[1000001]，其中a[i]保存给定整数中i的个数。输入时统计每个整数i出现的次数。这样可以对数组a按下标从小到大遍历，对应的整数也正好从小到大。

        由于一个对子用2个整数，一个顺子用3个整数。因此，优先考虑对子。

        前两个整数不可能存在顺子，所以挑对子。从第3个整数开始，先判断能否与前面的剩下的整数形成顺子（只需要出一个整数就使得cnt+1），不能形成顺子再考虑对子。

       （2）源程序。

#include

#include

int a[1000001];

int main()

{

    int n;

    while (scanf("%d",&n)!=EOF){

        memset(a,0,sizeof(a));

        int i,x,max=0;

        for (i=1;i<=n;i++){

            scanf("%d",&x);

            if (max

            a[x]++;

        }

        int ans=a[1]/2;

        a[1]=a[1]%2;

        for (i=2;i<=max;i++)

        {

            if (a[i-1]==1 && a[i-2]==1 && a[i]>0){

                a[i]--;  a[i-1]--;  a[i-2]--;

                ans++;

            }

            ans+=a[i]/2;

            a[i]%=2;

        }

        printf("%d\n",ans);

    }

    return 0;

}

        注：将此源程序提交给HDU6188 Duizi and Shunzi（http://acm.hdu.edu.cn/showproblem.php?pid=6188）可以Accepted。 

【例8】平衡字符串。

问题描述

有n个由“（”和“）”组成的字符串s1、s2、…、sn。将这n个字符串重新排序后，把它们连接起来，得到一个新的字符串t。设f（t）为t的最长平衡子序列（不必连续）的长度。所有可能t的f（t）的最大值为多少？

如下类型的字符串称为平衡字符串：

（1）如果是空字符串；

（2）如果A和B是平衡的，AB是平衡的；

（3）如果A是平衡的，（A）是平衡的。

输入

有多个测试用例。输入的第一行包含一个整数T，表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数n（1≤N≤105）表示字符串的数目。

接下来的n行中的每一行都包含一个字符串si，由“（”和“）”组成。

输出

对于每个测试用例，输出一个表示答案的整数。

输入样例

)()(()(

)(

输出样例

         （1）编程思路。

        先把每个字符串里面能匹配的括号全部配对抵消并计数，剩下的一定是由p个右括号+q个左括号组成的字符串。形如下列4种情况：)))))、 (((((((( 、))(((((( 、))))))))((。要使平衡子序列（不必连续）的长度最长，则需要最大化利用所有的剩余括号，即把左括号尽可能多的放在左边，右括号尽可能多的放在右边。

        对于消除匹配的括号后的4种剩余串，如果只包含左括号（形如“((((((((”）则把它放在左边，如果只有右括号（形如“)))))”）则把它放在右边。对于形如“))((((((”、“))))))))((”的剩余串采用的贪心策略如下：

        1）若两个字符串都是左括号多右括号少，就让右括号多的放右边；

        2）若两个字符串都是左括号少右括号多，就让左括号多的放左边；

        3）若一个字符串左括号多右括号少，一个左括号少右括号多，让左括号多的放左边；

        4）若一个字符串左括号少右括号多，一个左括号多右括号少，让左括号多的放左边。

        （2）源程序。

#include

#include

using namespace std;

struct node

{

   int left, right;

};

struct node a[100001];

char str[100001];

int cmp(struct node a, struct node b)

{

    if (a.left<=a.right && b.left>b.right) return 0;

    if (a.left>a.right && b.left<=b.right) return 1;

    if (a.left<=a.right && b.left<=b.right) return a.left>=b.left;

    return a.right<=b.right;

}

int main(void)

{

    int t;

    scanf("%d", &t);

    while (t--)

    {

        long long ans = 0;

        int n,i,j;

        scanf("%d", &n);

        for (i=0; i

        {

            a[i].left=a[i].right=0;

            scanf("%s", str);

            for (j = 0; str[j]!='\0'; j++)

            {

                if (str[j] == '(')

                    a[i].left++;

                else

                {

                    if (a[i].left)

                    {

                        a[i].left--;

                        ans++;

                    }

                    else

                    {

                        a[i].right++;

                    }

                }

            }

        }

        sort(a,a+n,cmp);

        int cnt=a[0].left;

        for (i = 1; i < n; i++)

        {

            if (cnt>= a[i].right)

            {

                ans += a[i].right;

                cnt -= a[i].right;

            }

            else

            {

                ans += cnt;

                cnt = 0;

            }

            cnt+=a[i].left;

        }

        printf("%lld\n", ans * 2);

    }

    return 0;

}

        注：将此源程序提交给HDU6299 Balanced Sequence（http://acm.hdu.edu.cn/showproblem.php?pid=6299）可以Accepted。 

【例9】自然数序列。

问题描述

给定自然数序列ai，ai∈[0,n]，ai≠aj( i≠j )，求自然数序列bi，使ai与bi对应位上的每一个数进行异或运算后相加和最大。

输入

有多个测试用例。

对于每个测试用例，第一行包含一个整数n（1≤ N≤ 105），第二行包含a0、a1、a2、…、an。

输出

对于每个测试用例，输出两行。第一行包含最大的异或和。第二行包含n+1个整数b0、b1、b2、…、bn。每两个整数间有一个空格。不要在bn之后输出任何空格。

输入样例

2 0 1 4 3

输出样例

20

1 0 2 3 4

         （1）编程思路。

        为了使异或运算之后相加和最大，采用的贪心策略是：使每一个对应位异或后能取得最大值。两个整数转化为二进制时，若每一位互补时，它们异或后能取得最大值。例如5（00000101）和10（00001010）互补，6（00000110）和9（00001001）也互补。

        因此本题的实质要求出0~n中每个整数的异或互补数。一个最简单的策略是对于整数k的二进制形式，把0换成1，1换成0，就可得到它的互补数，两个数亦或后将得到全1的最大数。

        在具体求0~n中每个整数p的互补数q时，定义数组b[]，其中b[i]的值表示整数i的互补数，数组b所有元素初始值全置为-1。然后从大到小求，即先求n的互补数，再求n-1的互补数，…。若某整数b[p]==-1，则求出p的互补数q，同时置b[p]=q，b[q]=p，之后不用求q的互补数了，即若某整数b[p]>=0，则表示其互补数已求出，直接跳过。

        为什么从大到小求呢？因为在求互补数时，对于任意一个数p，只有两种情况，一是其异或互补数q比它小，二是其异或互补数q比它大。如果异或互补数q比它小，则q对应的二进制数第一位肯定是0，后面可能会跟若干个0。最坏是全1这种（例如整数15），对应的是0；如果异或互补数q比它大，则q对应的二进制位数一定比p这个数长。例如，整数15（1111）对应的异或互补数可能是16（10000）、48（110000）等等。因此，从大到小求异或互补数，就可以避免上面不好处理的情况。例如，若n=48，先求48（110000）的互补数，为15（1111），再求47（101111）的互补数，为16（10000），…。若n=16，先求16（10000）的互补数，为15（1111），再求15（1111）的互补数，已求出为16（10000），跳过…。若n=15，先求15（1111）的互补数，为0（0000），再求14（1110）的互补数，为1（0001），…。

        （2）源程序。

#include

#include

int main()

{

    int n;

    while (scanf("%d", &n) != EOF){

        int a[100001], b[100001];

        int i,k;

        for (i = 0; i<=n; i++)

            scanf("%d", &a[i]);

        long long sum = 0;

        memset(b,-1,sizeof(b));

        int v,val,p;

        for (i=n; i>=0; i--){

           if (b[i]>=0)

              continue;

           k = i;

           p = 1;

           val = 0;

           while (k!=0){

               v = k & 1;

               val+=(v^1)*p;

               p <<= 1;

               k >>= 1;

           }

           b[i] = val;

           b[val] = i;

        }

        for (i=0; i<=n; i++)

            sum += a[i]^b[a[i]];

        printf("%lld\n", sum);

        for (i=0; i<=n; i++)

        {

            if (i!=0) printf(" ");

            printf("%d",b[a[i]]);

        }

        printf("\n");

    }

    return 0;

}

        注：将此源程序提交给HDU 5014 Number Sequence（http://acm.hdu.edu.cn/showproblem.php?pid=5014）可以Accepted。 

【例10】拆分。

问题描述

给定一个数自然数N（N<=109），将它拆分成若干各不相同的自然数Ai，满足ΣAi=N，且要求ΠAi（累乘）最大。

现在你能解决这个问题吗？（因为最后的数字太大，你的答案将是模10^9+7）

输入

第一行是一个整数T，表示测试用例的数量。

然后跟着T行。每行包含一个整数N。

输出

你能得到的最大累乘积（模为10^9+7）。

输入样例

20

输出样例

720

        （1）编程思路。

        要使累乘的积最大，则拆分出来的自然数（1得除外）的个数应尽可能多。

        例如，9可拆分为2+7、4+5、2+3+4，显然2+3+4的拆分方法最优。

　　因此，拆分的贪心策略为：尽可能将N拆分为以2为首项的连续递增序列，即把N拆成2+3+…+x<=N。

        先求出x，之后看N还多了多少，设R=N-(2+3+…+x)，就把后面的R项依次+1，变成2+3+...+y+(y+2)+(y+3)+...+(x+1)。

        特殊情况是，若从2到x都加1之后还剩余1，这时候把最后一项再加1，变成3+4+...+x+(x+2)。

        为求累乘积方便，采用乘法逆元进行处理。

       （2）源程序。

#include

#include

const long long MOD=1000000007;

int main()

{

    long long f[45000];

    int sum[45000];

    int inv[45000];

    inv[1]=1;f[1]=1;sum[1]=0;

    int i;

    for (i=2; i<45000;i++){

        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD; // 乘法逆元

        f[i]=(f[i-1]*i)%MOD;                  // 前缀乘

        sum[i]=sum[i-1]+i;                   // 前缀和（从2开始）

    }

    int t;

    scanf("%d",&t);

    while (t--){

        int n;

        scanf("%d",&n);

        if(n<5) {

            printf("%d\n",n);

            continue;

        }

        int left=2;

        int right=45000;

        while (left+1

             int mid=(left+right)/2;

             if (sum[mid]>n) right=mid;

             else left=mid;

        }

        int k=n-sum[left];

        long long ans;

        if (2+k>left){

            ans=f[left]*inv[2]%MOD*(k+2)%MOD;

            printf("%lld\n",ans);

        }

        else{

            ans=f[left]*inv[left+1-k]%MOD*(left+1)%MOD;

            printf("%lld\n",ans);

        }

    }

    return 0;

}

        注：将此源程序提交给HDU 5976 Detachment（http://acm.hdu.edu.cn/showproblem.php?pid=5976）可以Accepted。 

        在理解了贪心法及其应用方法的基础上，可以刷一下如下的HDU题库中的10道题目。这几道题目均可以采用贪心法解决。

         HDU 2570 迷瘴（http://acm.hdu.edu.cn/showproblem.php?pid=2570）

// 要让最后的体积最大，需要先加入浓度小的。贪心策略是：按浓度从小到大加入。
#include 
int main(void)
{
    int c;
    scanf("%d",&c);
    while(c--)
    {
        int n,v,w;
        scanf("%d%d%d",&n,&v,&w);
        int i,j,p[101];
        for(i=0; i)
            scanf("%d",&p[i]);
        for (i=0;i1;i++)
            for (j=0;j1-i;j++)
               if (p[j]>p[j+1])
               {
                  int t=p[j]; p[j]=p[j+1]; p[j+1]=t;
               }
        double sum=0.0;
        for (i=0; i)
        {
            if (sum+p[i] <= w*(i+1))
                sum+=p[i];
            else break;
        }
        if(!sum)
            printf("0 0.00\n");
        else
            printf("%d %.2f\n",v*i,sum/(i*100));
     }
    return 0;
}
HDU 2570 参考源程序

        HDU3177 Crixalis's Equipment（http://acm.hdu.edu.cn/showproblem.php?pid=3177）

// 当前物品能否放进山洞取决于当前物品的的移动体积是否小于山洞当前的剩余体积。贪心策略是：每次向山洞中放移动体积和停放体积差值最大的那个物品。
#include 
struct node
{
    int a,b;
};
int main()
{
    int t;
    scanf("%d",&t);
    while (t--){
        int v,n;
        scanf("%d%d",&v,&n);
        struct node e[1001];
        int i,j;
        for (i=0;i){
            scanf("%d%d",&e[i].a,&e[i].b);
        }
        for (i=0;i1;i++){
            for (j=0;j1-i;j++){
                if (e[j].a+e[j+1].b>e[j+1].a+e[j].b){
                    struct node tmp;
                    tmp=e[j];  e[j]=e[j+1]; e[j+1]=tmp;
                }
            }
        }
        for (i=0;i)
        {
            if (vbreak;
            v-=e[i].a;
        }
        if (i0) printf("No\n");
        else   printf("Yes\n");
    }
    return 0;
}
HDU 3177 参考源程序

        HDU3348 coins（http://acm.hdu.edu.cn/showproblem.php?pid=3348）

// 求最少的数量采用的贪心策略是：优先取面值尽量大的纸币来凑这个价格。
// 求最多的数量通过贪心来凑出sum-n（sum为所有给定纸币的总价格，n为题目要求凑的价格）的最小纸币数x，则凑出n的最大纸币数 = 总纸币数 – x。
#include 
int v[5] = {1,5,10,50,100};
int a[5];
int calc(int value)
{
    int res = 0;
    int i,t;
    for (i = 4;i >=0;i--)
    {
        if (value >= v[i])
        {
            t = (value/v[i])v[i]:a[i];
            value -= v[i] * t;
            res += t;
        }
    }
    if (value != 0)
        return -1;
    return res;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int p,i;
        int sum = 0, num = 0;
        scanf("%d",&p);
        for (i=0;i<5;i++)
        {
            scanf("%d",&a[i]);
            num += a[i];
            sum += v[i] * a[i];
        }
        int res_min = 0, res_max = 0;
        res_min = calc(p);
        res_max = calc(sum - p);
        if (res_min == -1 || res_max == -1)
            printf("-1 -1\n");
        else
            printf("%d %d\n",res_min,num - res_max);
    }
    return 0;
}
HDU 3348 参考源程序

        HDU 3661  Assignments（http://acm.hdu.edu.cn/showproblem.php?pid=3661）

// 贪心策略是：将数组A从小到大排序，数组B从大到小排序。然后逐项匹配，每次让A中的最小和B中的最大匹配。
#include 
int main()
{
    int n,t;
    while(scanf("%d%d",&n,&t)!=EOF)
    {
        int a[1001],b[1001];
        int i,j,tmp;
        for (i=0;i)
            scanf("%d",&a[i]);
        for (i=0;i)
            scanf("%d",&b[i]);
        for (i=0;i1;i++)
            for (j=0;j1-i;j++)
               if (a[j]>a[j+1])
               {
                   tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp;
               }
        for (i=0;i1;i++)
            for (j=0;j1-i;j++)
               if (b[j]1])
               {
                   tmp=b[j]; b[j]=b[j+1]; b[j+1]=tmp;
               }
        int ans=0;
        for (i=0;i)
        {
            if (a[i]+b[i]>t)
               ans += a[i]+b[i]-t;
        }
        printf("%d\n",ans);
    }
    return 0;
}
HDU 3661 参考源程序

        HDU 3979 Monster（http://acm.hdu.edu.cn/showproblem.php?pid=3979）

// 设打第i只怪兽的耗时为ti，怪兽攻击力为gi，
// 贪心策略是按gi/ti的比值由大到小的顺序消灭怪兽。
#include 
#include 
using namespace std;
struct Node
{
    int hp,g;
};
int n,m;
int  cmp(struct Node a,struct Node b)
{
    return a.hp*b.g < b.hp*a.g;
}
int main()
{
    struct Node monster[10010];
    int t,iCase;
    scanf("%d",&t);
    for (iCase=1;iCase<=t;iCase++){
        int n,m,i;
        scanf("%d%d",&n,&m);
        for (i=0;i)
        {
            scanf("%d%d",&monster[i].hp,&monster[i].g);
            monster[i].hp = (monster[i].hp + m - 1)/m;
        }
        sort(monster,monster+n,cmp);
        long long ans = 0;
        int cnt = 0;
        for(int i = 0;i < n;i++)
        {
            cnt += monster[i].hp;
            ans += (long long)cnt*monster[i].g;
        }
        printf("Case #%d: %lld\n",iCase,ans);
    }
    return 0;
}
HDU 3979 参考源程序

        HDU 4310 Hero（http://acm.hdu.edu.cn/showproblem.php?pid=4310）

// 贪心策略是：将血量少攻击高的敌人优先打死。也就是按DFS/HP的比值从大到小排序，将比值大的敌人优先杀死。
#include 
struct node
{
    long long dps,hp;
};
int main()
{
    int n;
    struct node a[21];
    while (scanf("%d",&n)!=EOF){
        int i,j;
        long long sum=0;
        for (i=0;i){
            scanf("%lld%lld",&a[i].dps,&a[i].hp);
            sum+=a[i].dps;
        }
        for (i=0;i1;i++)
            for (j=0;j1-i;j++)
              if (a[j].dps*a[j+1].hp1].dps*a[j].hp){
                 struct node tmp;
                 tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp;
              }
        long long ans=0;
        for (i=0;i){
            ans+=sum*a[i].hp;
            sum-=a[i].dps;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
HDU 4310 参考源程序

        HDU4803 Poor Warehouse Keeper（http://acm.hdu.edu.cn/showproblem.php?pid=4803）

// 由于y的范围比较大，无法用搜索方法去解决。
// 对于两种操作，x+1，斜率（单价）不会发生改变，而y+1,会使得斜率变大。
// 执行x+1的次数是固定的(x-1）次，所以只要执行第二个操作的最小次数就行。
// 采取的贪心策略是：每次都把y加到符合最大的斜率。
#include 
#define eps 1e-6
int main(void)
{
    int x;
    double y;
    while (scanf("%d%lf",&x,&y)!=EOF){
        if (1.0*x>y) {   // 由于斜率始终是增加的，不会小于1
             printf("-1\n");
             continue;
        }
        double  dy = 1.0;
        double maxk = (y+1-eps)/x;
        // 代表目标最大的斜率。因为只显示整数部分，所以，y.9999999是最大的。
        int ans = x-1;
        int i;
        for (i=1;i<=x;i++){
            int  add = i*maxk-dy;  // 表示当前坐标能达到的最大y所增加的。
            ans += add;
            dy += add;
            dy += (dy/i);  // 执行i+1后y的变化。
        }
        printf("%d\n",ans);
    }
    return 0;
}
HDU 4803 参考源程序

       HDU4864 Task（http://acm.hdu.edu.cn/showproblem.php?pid=4864）

// 由于在报酬构成中，x的权重远大于y的权重。因此将任务按照x降序排列，x相同时按照y降序排列。对于一个任务可以选择的是所有x1>x的机器，而在这些机器中选择最小的y1，因为这样选就可以保留比较大的y1使其去匹配后面的任务。
#include 
#include <string.h>
#include 
using namespace std;
struct node
{
    int x, y;

};
struct node machine[100001], task[100001];
int cmp(struct node a,struct node b)
{
    if(a.x!=b.x) return a.x > b.x;
    return a.y > b.y;
}
int main()
{
    int n,m;
    while (scanf("%d%d", &n,&m)!=EOF)
    {
        int i,j,k;
        for (i=0; i)
            scanf("%d%d", &machine[i].x, &machine[i].y);
        for (i=0; i)
            scanf("%d%d", &task[i].x, &task[i].y);
        sort(machine, machine+n,cmp);
        sort(task, task+m,cmp);
        int num = 0;
        long long money = 0;
        int s[150];
        memset(s, 0, sizeof(s));
        j = 0;
        for (i=0; i)
        {
            while(j=task[i].x)
            {
                s[machine[j].y]++;
                j++;
            }
            for (k=task[i].y; k<=100; k++)
                if(s[k]>0)
                {
                   num++;
                   money += 500*task[i].x + 2*task[i].y;
                   s[k]--;
                   break;
                }
        }
        printf("%d %lld\n", num, money);
    }
    return 0;
}
HDU 4864 参考源程序

       HDU 6563 Strength（http://acm.hdu.edu.cn/showproblem.php?pid=6563）

#include 
#include 
using namespace std;
struct node{
    long long s, v;
};
struct node a[100001], b[100001];
int cmp(struct node x, struct node y)
{
    return x.s<y.s;
}
int main()
{
    int t,iCase;
    scanf("%d",&t);
    for (iCase = 1; iCase <= t; iCase++){
        int n,m;
        scanf("%d%d",&n,&m);
        int i,num = 0;
        for (i=0;i)
            scanf("%lld",&a[i].s);
        for (i=0;i)
            scanf("%lld",&b[i].s);
        for (i=0;i)
            scanf("%lld",&b[i].v);
        long long res1 = 0, res2 = 0;
        int  left = 0, right = n-1;
        sort(a, a+n,cmp);
        sort(b, b+m,cmp);
        while (left= 0){
            while (left;
            if (left>=m || b[left].s > a[right].s) break;
            res1 += (a[right].s - b[left].s);
            right--;
            left++;
        }
        left = m-1, right = n-1;
        while (left >=0 || right >= 0){
            if (right<0) break;
            if (a[right].s < b[left].s){
                res2 = 0;
                break;
            }
            else if(!b[left].v){
                res2 += a[right].s - b[left].s;
            }
            else if(left<0) res2 += a[right].s;
            if (left>=0) left--;
            if (right>=0) right--;
        }
        printf("Case %d: %lld\n",iCase,res1>res2?res1:res2);
    }
    return 0;
}
HDU 6563 参考源程序

        HDU 6709 Fishing Master（http://acm.hdu.edu.cn/showproblem.php?pid=6709）

// 设num=∑(a[i]/k)，
// 若num>=(n-1)，此时每烹饪一条鱼i，同时抓（a[i]/k）条鱼即可保证除去K外的每一份时间都在烹饪鱼。
// 若num<(n-1)，此时，要使浪费的时间最少，则需以（k-a[i]%k）从小到大的顺序抓捕和烹饪鱼。
#include 
#include
using namespace std;
int k;
int cmp(int x,int y)
{
    return (k-x%k)<(k-y%k);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d%d",&n,&k);
        int a[100001];
        int num=0;
        long long ans=k;
        int i;
        for (i=1;i<=n;i++){
            scanf("%d",&a[i]);
            num+=a[i]/k;
            ans+=a[i];
        }
        if (num1){
            sort(a+1,a+1+n,cmp);
            num=n-num-1;
            for (i=1;i<=num;i++){
                ans+=(k-a[i]%k);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}
HDU 6709 参考源程序
CC++程序设计

相关

标签