卡片游戏（hdu4550）贪心

时间：2023-01-23 21:29:13

卡片游戏

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 913    Accepted Submission(s): 291

Problem Description
　　小明最近宅在家里无聊，于是他发明了一种有趣的游戏，游戏道具是N张叠在一起的卡片，每张卡片上都有一个数字，数字的范围是0~9，游戏规则如下： 　　首先取最上方的卡片放到桌子上，然后每次取最上方的卡片，放到桌子上已有卡片序列的最右边或者最左边。当N张卡片全部都放到桌子上后，桌子上的N张卡片构成了一个数。这个数不能有前导0，也就是说最左边的卡片上的数字不能是0。游戏的目标是使这个数最小。 　　现在你的任务是帮小明写段程序，求出这个最小数。
 
Input
第一行是一个数T，表示有T组测试数据； 然后下面有T行， 每行是一个只含有0~9的字符串，表示N张叠在一起的卡片，最左边的数字表示最上方的卡片。
[Technical Specification] T<=1000 1 <= N <= 100
 
Output
对于每组测试数据，请在一行内输出能得到的最小数。
 
Sample Input
3
565
9876543210
9876105432
 
Sample Output
556
1234567890
1678905432
 
//此题应首先选择一种贪心策略，本题的贪心策略为首先找到最右端的非零最小的值，然后对于其左边的数字可以根据具体情况左右插，而右边的则只能接到最后面了，最终即可选择满足条件的最小值
 
自己开始做的时候，没看到N的取值，用int定义，然后果断发现错了，，然后改数组做，但是WA了。。。
然后在网上找了测试数据，发现自己开始想的太简单了，
so。。╮(╯▽╰)╭
 
 
#include<iostream>

#include<string>

using namespace std;

int main()

{

    string str;

    int i,t,j;

    char max;

    cin>>t;

    while(t--)

    {

        cin>>str;

        max='';

        for(i=;i<str.size();i++)//需找最左边的非零最小数字

        {

            if(str[i]!=''&&max>=str[i])

            {

                max=str[i];

                j=i;

            }

        }

        string min;

        min=str[];

        for(i=;i<str.size();i++)

        {

            if(i<j)

            {

                if(str[i]>min[])

                    min=min+str[i];

                else if(str[i]<=min[])

                    min=str[i]+min;

            }

            else if(i==j)

            {

                min=str[i]+min;

            }

            else if(i>j)

            {

                min=min+str[i];

            }

        }

        cout<<min<<endl;

    }

    return ;

}

顺便学习了了一下string类型的用法：

5. 两个string对象相加

string对象的加法被定义为连接（concatenation）。也就是说，两个（或多个）string对象可以通过使用加操作符+或者复合赋值操作符+=（1.4.1节）连接起来。给定两个string对象：

string s1("hello, ");

string s2("world\n");

下面把两个string对象连接起来产生第三个string对象：

string s3 = s1 + s2;      // s3 is hello, world\n

如果要把s2直接追加到s1的末尾，可以使用+=操作符：

s1 += s2;      // equivalent to s1 = s1 + s2

so：要好好学习c++；

 

相关文章