安利一波答案 经典算法设计

 

1、键盘输入一个高精度的正整数N,去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小。输入数据均不需判错。输出应包括所去掉的数字的位置和组成的新的正整数(N不超过240位)

算法分析:将N存在字符串中,模拟数据运算。

算法设计:若高位高于地位则删除高位,由前往后去除S位。若遍历字符串后删除位数小于S则删去最末尾几位,直到满足删除S的条件,同时输出前去除首位的0。

代码:

#include<iostream>
#include<string>
using namespace std;

void getmin(string &n,int &s,int k)//递归判断是否删去
{
    for(int i=k; i<n.size()-1; i++)
    {
        if (n[i]>n[i+1])
        {
            n.erase(i,1);
            getmin(n,--s,i-1);
        }
    }
}

int main()
{
    string n;
    int s;
    cin>>n>>s;
    getmin(n,s,0);
    while(s>0)//若删去位数小于S,删去末尾至满足条件
    {
        n.erase(n.size()-1,1);
        s--;
    }
    n.erase(0,n.find_first_not_of('0'));//去除首位的0
    if (n.empty())//若S与N的位数相等输出0
    {
        n="0";
    }
    cout<<n<<endl;
}

Hide:

1.string.erase(pos,n); 删除从pos开始的n个字符,比如erase(0,1)就是删除第一个字符;

2.string.find_first_not_of(char);返回字符串第一个不是char的值的位置;


2、某单位给每个职工发工资(精确到元)。为了保证不要临时兑换零钱, 且取款的张数最少,取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编程完成。

算法分析:建立员工工资类,各种币值设置为静态成员。

算法设计:分别为每个员工求出各种币值的张数再求和。

代码:

#include<iostream>
using namespace std;
class yg
{
public:
    yg(int a=0):gz(a){}
    void setgz(int a)
    {
        gz=a;
        fun();
    }
    void fun()
    {
        m100+=gz/100;gz%=100;
        m50+=gz/50;gz%=50;
        m20+=gz/20;gz%=20;
        m10+=gz/10;gz%=10;
        m5+=gz/5;gz%=5;
        m2+=gz/2;gz%=2;
        m1+=gz;
    }
    static int m100,m50,m20,m10,m5,m2,m1;
private:
    int gz;
};
int yg::m100=0,yg::m50=0,yg::m20=0,yg::m10=0,yg::m5=0,yg::m2=0,yg::m1=0;//初始化
int main()
{
    int n,g;
    cin>>n; //输入员工数
    yg *p=new yg[n];
    for(int i=0;i<n;i++)
    {
        cin>>g;//分别输入员工工资
        p[i].setgz(g);
    }
    cout<<yg::m100<<" "<<yg::m50<<" "<<yg::m20<<" "<<yg::m10<<" "<<yg::m5<<" "<<yg::m2<<" "<<yg::m1<<endl;
}

 


3、有形如下图所示的一个数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的数值和最大。

9

12    15

10     6      8

2    18      9    5

19     7     10    4   16

算法分析:二位数组储存数塔。

算法设计:由倒数第二层开始往上层更新节点为由这个点到底部的最大值,塔尖得数为答案。

代码:

#include<iostream>
using namespace std;
int a[5+2][5+2];
int main()
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<=i;j++)
            cin>>a[i][j];
    }
    for(int i=3;i>=0;i--)
    {
        for(int j=0;j<=i;j++)
        {
            a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
        }
    }
    cout<<a[0][0]<<endl;
}

相关日志

  1. 2016.06.18

    竞赛技巧:读取一行到string类

    string类中定义了getline函数; …

  2. 2016.07.10

    Codeforces Round #361 (Div. 2)A. Mike and Cellphone

    果然CF是三亿coder的coding梦想(…

  3. 2016.05.11

    ZOJ 3704 I am Nexus Master!(模拟)

    题目链接:http://acm.zju.ed…

  4. 2016.05.12

    ZOJ 3698 Carrot Fantasy(搜索大模拟)

    题目地址:http://acm.zju.ed…

  5. 2016.05.04

    FZU 2041 checker(搜索)

    题目链接:http://acm.fzu.ed…

  6. 2016.07.10

    Codeforces Round #361 (Div. 2)B. Mike and Shortcuts

    题意迷之简短。大意就是:一个城市i到另一个城…

评论

还没有评论。

在此评论中不能使用 HTML 标签。