C语言上机作业（贪心专题）

Problem A: 找钱问题

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 11964 Solved: 3340

Description

买火车票时经常会碰到找钱问题。售票员手中有50、20、10、5、1元的钱币，你知道怎么找钱才能使找回的零钱张数最少吗？

Input

多组测试数据，输入需要找钱的钱数

Output

输出按下面格式：第一行输出"change:",然后是你要找的钱以下几行按面值从大到小输出要找的张数，格式如下：50 yuan: 1,如果1张也没有就不需要输出

Sample Input

Sample Output

change:76
50 yuan: 1
20 yuan: 1
5 yuan: 1
1 yuan: 1

这道题按照题意模拟下就好了，注意下输出格式

#include <stdio.h>
 
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        printf("change:%d
",n);
        int a = 0;
        a = n / 50;
        n %= 50;
        int b = 0;
        b = n / 20;
        n %= 20;
        int c = 0;
        c = n / 10;
        n %= 10;
        int d = 0;
        d = n / 5;
        n %= 5;
        int e = 0;
        e = n / 1;
        n %= 1;
        if(a)printf("50 yuan: %d
",a);
        if(b)printf("20 yuan: %d
",b);
        if(c)printf("10 yuan: %d
",c);
        if(d)printf("5 yuan: %d
",d);
        if(e)printf("1 yuan: %d
",e);
    }
    return 0;
}

View Code

Problem B: Computer Arrangement

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 2686 Solved: 985

Description

每年新学期，计算中心的老师都要安排上机时间。现设有n个班级E={1, 2, 3, ..., n}, 要使用8号机房，同一时间内只允许一个班级使用该机房。设班级i上机的起止时间区间为[si,fi),如果班级i使用了8号机房, 则它在时间[si,fi)内占用该机房，若区间[si,fi)和[sj,fj)不相交，则称班级i和j均可安排上机的。现在要求你安排一下上机情况，使尽可能多的班级能有机会上机。

Input

有多组测试数据。第1行先输入整数t(1<= t <= 100),表示共有t组测试数据。每组测试数据输入共有3行，第1行为一个整数n(1 <＝ n <＝ 2000) 表示班级数第2行共n个整数，为这n个班级希望上机的开始时间(以某一时间为基准）第3行共n个整数，为这n个班级上机的终止时间

Output

对于每个测试案例输出最多可以安排上机的班级

Sample Input

1
11
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14

Sample Output

4
与那道今年暑假不AC是同样的思路，按照结束时间早晚进行排序，结束早的在前，纯c写的就冒泡排了一边，然后从第一个时间段记录下结束时间，判断下一个的开始时间是不是比记录的结束时间晚或者两者相等，如果满足条件就答案加一，并把结束时间更新，否则判断下一个时间段。

#include<stdio.h>
#include<string.h>
//#define Debug
struct Ac{
    int beginn;
    int endd;
}ac[2005];
int main()
{
    #ifdef Debug
        freopen("Text.txt","r",stdin);
    #endif // Debug
    int temp,t,i,j,n;
    scanf("%d",&t);
    while(t--){
        memset(ac,0,sizeof(ac));
        scanf("%d",&n);
        for(i = 0;i < n;i++){scanf("%d",&ac[i].beginn);}
        for(i = 0;i < n;i++){scanf("%d",&ac[i].endd);}//输入
        for(i = 0;i < n;i++){
            for (j = i+1;j <n;j++){
                if(ac[j].endd < ac[i].endd){
                    temp = ac[i].endd;
                    ac[i].endd = ac[j].endd;
                    ac[j].endd = temp;
                    temp = ac[i].beginn;
                    ac[i].beginn = ac[j].beginn;
                    ac[j].beginn = temp;
                }
            }
        }//冒泡排序
        int sta = ac[0].endd;
        int ans = 1;
        for( int i = 1; i < n; i++)
        {
            if( ac[i].beginn >= sta ) ans++, sta = ac[i].endd;
        }
        printf("%d
",ans);
    }
}

View Code

Problem D: Delete Number

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 5203 Solved: 1741

Description

Given 2 integer number n and m. You can delete m digits from the number n, then number n changes to a new number n1. Tell me how to delete the number, you can get the smallest one. For example,

 m: 1        n: 1456
 n1 may be 145, 156, 146, 456
 the smallest one is 145. Then n1 should be 145.

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case consists of one single line containing two integer number m(1 <= m <= 1000), and n(1 <= n < 101000).

Output

Your program must output a single line for each test case. The line should contain the number n1.

Sample Input

1
1 1456

Sample Output

HINT

if the number is 000345 you should output 345

给定一个高精度数字，删除其中m个数字，使其在原顺序保持不变的情况下获得最小值。

对于一串数字，同一个数字位于前面对整串数的大小贡献比后面的大

例如：131234

删除前面的3得到 11234，而删除后面的3得到 13124

此时还可以发现这种数字一般满足后面一位小于它，131234中第一个3后面的1比3小，故删除3；

则只需要遍历数字串s寻找满足s[i+1]<s[i]的位置，删除或整串向前覆盖即可。

如果整串数字满足递增，例如：123456

则删除最后一位即可，因为此时删除第一位或最后一位整串数字长度相同，显然删除最后一位会使数更小；

最后输出时注意将前导0删除或跳过输出即可

#include<stdio.h>
#include<string.h>
//#define Debug
char s[100005];
int main()
{
    #ifdef Debug
        freopen("Text.txt","r",stdin);
    #endif // Debug
    int t;
    while(~scanf("%d",&t)){
    while( t-- )
    {
        int n;
        scanf("%d %s",&n,s);
        int len = strlen(s);
        if( n >= len ) { puts("0"); continue; }
        int flag = 1;
        while(n&&flag){
            flag = 0;
            for( int i = 0; i < len-1; i++)
            {
                if( s[i] > s[i+1] )
                {
                    for( int j = i; j < len-1; j++)
                    {
                        s[j] = s[j+1];
                    }
                    s[len-1] = '';
                    len--;
                    n--;
                    i=-1;
                    flag = 1;
                }
                if(!n) break;
            }
        }
        int cnt = 0;
        while( s[cnt] == '0' ) {cnt++;}
        for( int i = cnt; i < len-n; i++)
        {
            printf("%c",s[i]);
        }
        if(cnt >= len-n || len == 0 ) printf("%d
",0);
        else printf("
");
    }
    }
    return 0;
}

View Code

其他题目各位巨佬的博客上都有，百度即可找到，就不再写了。。。。。。