机试-经典入门

##排序

c++ 快速排序库函数，头文件需包含 algorithm，并使用标准命名空间(sort 被定义在其中)，我们也可以定义新的排序规则：

#include<stdio.h>
#include<algorithm>
using namespace std;
// sort 逆序

bool cmp(int x, int y){        //定义排序规则
    return x>y;
}

int main(){
    int n;
    int buf[100];

    while(scanf("%d", &n) != EOF){
        for (int i=0;i<n;i++){
            scanf("%d", &buf[i]);
        }

        sort(buf, buf+n, cmp);

        for (int i=0;i<n;i++){
            printf("%d ", buf[i]);
        }
        printf("\n");
    }
    return 0;
}

在 cmp 中，当它返回 true 时，表示 cmp 函数的第一个参数将会排在第二个参数之前。

在 sort() 中默认是以 < 来比较的，也就是升序，我们也可以重载 <。

• 例2.2 成绩排序：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
// 成绩 姓氏 年龄排序
// 重载运算符
struct E{
    char name[101];
    int age;
    int score;

    bool operator < (const E &b) const{        // 利用 c++ 运算符重载直接定义小于运算符
        if (score != b.score)
            return score < b.score;
        int tmp = strcmp(name, b.name);
        if (tmp != 0)
            return tmp < 0;
        else
            return age < b.age;
    }
}buf[1000];


int main(){
    int n;
    while (scanf("%d", &n) != EOF){
        for (int i=0;i<n;i++){
            scanf("%s%d%d", buf[i].name, &buf[i].age, &buf[i].score);
        }

        sort(buf, buf+n);

        for (int i=0;i<n;i++){
            printf("%s %d %d\n", buf[i].name, buf[i].age, buf[i].score);
        }
    }
    return 0;
}

日期类问题

在计算日期差值的问题中，我们进行预处理——空间换时间

#include<stdio.h>
#define ISYEAP(x) x%100 !=0 && x%4 == 0 || x%400 == 0?1:0

// 定义宏判断是否为闰年，方便计算天数
// 以空间换时间，将公元 0 - 5001 所有的天数保存下来

int dayOfMonth[13][2] = {
    0, 0,
    31, 31,
    28, 29,
    31, 31,
    30, 30,
    31, 31,
    30, 30,
    31, 31,
    31, 31,
    30, 30,
    31, 31,
    30, 30,
    31, 31
};

struct Date
{
    int Day;
    int Month;
    int Year;
    void nextDay(){
        Day ++;
        if (Day > dayOfMonth[Month][ISYEAP(Year)]){
            Day = 1;
            Month ++;
            if (Month > 12){
                Month = 1;
                Year ++;
            }
        }
    }
};

int buf[5001][13][32];

int Abs(int x){
    return x<0?-x:x;
}

int main(){
    Date tmp;
    int cnt = 0;
    tmp.Day = 1;
    tmp.Month = 1;
    tmp.Year = 0;

    while(tmp.Year != 5001){
        buf[tmp.Year][tmp.Month][tmp.Day] = cnt;
        tmp.nextDay();
        cnt ++;
    }

    int d1,m1,y1;
    int d2,m2,y2;
    while(scanf("%4d%2d%2d", &y1,&m1,&d1) != EOF){
        scanf("%4d%2d%2d", &y2,&m2,&d2);
        printf("%d\n", Abs(buf[y2][m2][d2] - buf[y1][m1][d1]) + 1);
    }
    return 0;
}

hash的应用

将存储位置与数据本身对应起来的手段就是 Hash。

统计同成绩学生的人数：

#include<stdio.h>
int main(){
    int n;
    while(scanf("%d", &n) != EOF && n!= 0){
        int Hash[101] = {0};

        for (int i=1;i<=n;i++){
            int x;
            scanf("%d", &x);
            Hash[x] += 1;
        }

        int x;
        scanf("%d", &x);

        printf("%d\n", Hash[x]);
    }
    return 0;
}

大数排序，选取前 m 大的数

#include<stdio.h>
#define OFFSET 500000

//hash数组输出前 m 大的数
int Hash[1000001] = {0};

int main(){
    int n,m;
    while(scanf("%d%d", &n, &m) != EOF){
        for (int i=1;i<=n;i++){
            int x;
            scanf("%d", &x);
            Hash[x+OFFSET] = 1;
        }

        for (int i=500000;i>=-500000;i--){
            if (Hash[i+OFFSET] ==1 ){
                printf("%d", i);
                m--;
                if (m!=0)
                    printf(" ");
                else{
                    printf("\n");
                    break;
                }
            }
        }
    }
    return 0;
}

注意由于输入数据出现了负数，所以需要对输入的数据加上一个固定的偏移值，使[-500000,500000] 映射到[0,100000]上。

排版题

对于所要求的图形不具有显著的规律性，我们需要先排版，然后再输出。

• 例2.8：叠框

#include<stdio.h>
int main(){
    int outPutBuf[82][82];
    char a,b;
    int n;
    bool firstCase = true; //是否为第一组数据标志
    while (scanf("%d %c %c", &n, &a, &b) == 3){
        if (firstCase == true)
            firstCase = false;
        else
            printf("\n");
        for (int i=1, j=1;i<=n;i+=2,j++){
            int x=n/2+1, y=x;
            x-=j-1;y-=j-1;
            char c=j%2==1?a:b;
            for (int k=1;k<=i;k++){
                outPutBuf[x+k-1][y] = c;
                outPutBuf[x][y+k-1] = c;
                outPutBuf[x+i-1][y+k-1] = c;
                outPutBuf[y+k-1][x+i-1] = c;
            }
        }
        if(n!=1){
            outPutBuf[1][1] = ' ';
            outPutBuf[1][n] = ' ';
            outPutBuf[n][1] = ' ';
            outPutBuf[n][n] = ' ';
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                printf("%c", outPutBuf[i][j]);
            }
            printf("\n");
        }
    }
}

查找

###二分查找：需要先进行升序排序。

• 例 2.10: 查找学生信息

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct Student{
    char no[100];
    char name[100];
    int age;
    char sex[5];
    bool operator < (const Student & A) const{
        return strcmp(no, A.no) < 0 ;
    }

}buf[1000];

int main(){
    int n;
    while (scanf("%d", &n) != EOF){
        for (int i=0; i<n;i++){
            scanf("%s%s%s%d", buf[i].no, buf[i].name, buf[i].sex, &buf[i].age);
        }
        sort(buf, buf+n);
        int t;
        scanf("%d", &t);
        while(t--!=0){
            int ans=-1;
            char x[30];
            scanf("%s", x);
            int top=n-1, base=0;
            while(top>=base){
                int mid = (top+base)/2;
                int tmp = strcmp(buf[mid].no, x);
                if (tmp==0){
                    ans=mid;
                    break;
                }
                else if(tmp>0)
                    top = mid-1;
                else
                    base = mid+1;

            }
            if(ans==-1){
                    printf("No Answer!\n");
            }
            else printf("%s %s %s %d\n", buf[ans].no, buf[ans].name, buf[ans].sex, buf[ans].age);

        }
    }
    return 0;
}

贪心算法

贪心是一种总是选择当前最好的选择，而不从整体上去把握的思想，但往往这种贪心策略能够得到接近最优的结果。但是贪心策略是否有效，需要我们从理论上证明，往往通过反证法。

• 例2.11 FatMouse’s Trade:

我们的策略是每次都买性价比最高的物品，直到钱被耗尽或物品被买完。

#include<stdio.h>
#include<algorithm>
using namespace std;
struct goods{
    double mass;
    double value;
    double ratio;
    bool operator < (const goods &A) const{
        return ratio > A.ratio;
    }
}buf[1000];

int main(){
    double m;
    int n;
    while (scanf("%lf%d", &m, &n) != EOF){
        if (m==-1 & n==-1)
            break;
        for (int i=0;i<n;i++){
            scanf("%lf%lf", &buf[i].mass, &buf[i].value);
            buf[i].ratio = buf[i].mass / buf[i].value;
        }
        sort(buf, buf+n);
        double mount_mass = 0;
        int idx = 0;
        while (m > 0 && idx < n){
            if (buf[idx].value > m){
                mount_mass += m*buf[idx].ratio;
                break; 
            }
            else{
                m -= buf[idx].value;
                mount_mass += buf[idx].mass;
                idx ++;
            }
        }
        printf("%.3lf\n", mount_mass);
    }

    return 0;
}

• 例2.12 今年暑假不 AC:

贪心策略是选择结束时间最早的。

#include<stdio.h>
#include<algorithm>
using namespace std;
struct program
{
    int startTime;
    int endTime;
    bool operator < (const program &A) const{
        return endTime < A.endTime;
    }
}buf[100];

int main(){
    int n;
    while (scanf("%d", &n) != EOF){
        if (n==0)
            break;
        for (int i=0;i<n;i++){
            scanf("%d%d", &buf[i].startTime, &buf[i].endTime);
        }
        sort(buf, buf+n);
        int currentTime = 0;
        int countProgram = 0;
        for (int i=0;i<n;i++){
            if (currentTime <= buf[i].startTime){
                countProgram ++;
                currentTime = buf[i].endTime;
            }
        }
        printf("%d\n", countProgram);
    }
    return 0;
}