《算法笔记》Day 3

1020 月饼 (25分)
月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：
每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：
对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

输入样例：

3 20
18 15 10
75 72 45

输出样例：

94.50

Code:

#include<stdio.h>
#include<algorithm>
using namespace std;
struct mooncake{
    double store;
    double sell;
    double price;
}cake[1001];
bool cmp(mooncake a,mooncake b){
    return a.price > b.price;
}
int main(void){
    int kind;
    double sum;
    scanf("%d %lf",&kind,&sum);
    int i,j;
    for(i=0;i<kind;i++){
        scanf("%lf",&cake[i].store);
    }
    for(i=0;i<kind;i++){
        scanf("%lf",&cake[i].sell);
        cake[i].price = cake[i].sell / cake[i].store;
    }
    sort(cake,cake + kind,cmp);
    double total = 0.0;
    double temp = 0.0;
    for(i=0;i<kind;i++){
        if(temp + cake[i].store >= sum){
            break;
        }
        total += cake[i].sell;
        temp += cake[i].store;
    }
    if(temp == sum){
        printf("%.2f",total);
        return 0;
    }
    else{
        total += (sum - temp) * cake[i].price;
        printf("%.2f",total);
        return 0;
    }
}

1023 组个最小数 (20分)
给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入格式：
输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

输出格式：
在一行中输出能够组成的最小的数。

输入样例：

2 2 0 0 0 3 0 0 1 0

输出样例：

10015558

Code:

#include<stdio.h>
#include<string.h>
int main(void){
    int a[10];
    memset(a,0,sizeof(a));
    int i,j;
    for(i=0;i<10;i++){
        scanf("%d",&a[i]);
    }
    for(i=1;i<10;i++){
        if(a[i] != 0){
            printf("%d",i);
            a[i]--;
            break;
        }
    }
    for(i=0;i<10;i++){
        for(j=0;j<a[i];j++){
            printf("%d",i);
        }
    }
    return 0;
}

1093 Count PAT’s (25分)
The string APPAPTcontains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT's contained in the string.

Input Specification:
Each input file contains one test case. For each case, there is only one line giving a string of no more than 10^​5 characters containing only P, A, or T.

Output Specification:
For each test case, print in one line the number of PAT's contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

APPAPT

Sample Output:

2

Code:

#include<stdio.h>
#include<string.h>
char a[100010];
int main(void){
    int i;
    scanf("%s",a);
    int len = strlen(a);
    int leftP[100010];
    int rightT[100010];
    memset(leftP,0,sizeof(leftP));
    memset(rightT,0,sizeof(rightT));
    int temp = 0;
    for(i=0;i<len;i++){
        if(a[i] == 'P'){
            temp++;
        }
        leftP[i] = temp;
    }
    temp = 0;
    for(i=len-1;i>=0;i--){
        if(a[i] == 'T'){
            temp++;
        }
        rightT[i] = temp;
    }
    temp = 0;
    for(i=0;i<len;i++){
        if(a[i] == 'A'){
            temp = (temp + rightT[i] * leftP[i]) % 1000000007;
        }
    }
    printf("%d",temp);
    return 0;
}