Day 9～PAT B1020，PAT B1023，区间贪心_每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 n 表示

简单贪心：总是考虑当前状态下的局部最优，以求全局最优

输入：每个输入包含一个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数以及不超过500（以万吨为单位）

的正整数D表示市场最大需求量；随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价

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

#include<stdio.h>
#include<algorithm>
using namespace std;
/*
    简单贪心：总是考虑当前状态下的局部最优，以求全局最优
    输入：每个输入包含一个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数以及不超过500（以万吨为单位）
    的正整数D表示市场最大需求量；随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价
    输出：对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后两位。
    
*/
struct moonCake{
    double inventory;        //库存量
    double totalPrice;     //总售价
    double averagePrice;        //均价
}mCake[1010];
 
bool cmp(moonCake a,moonCake b){
    return a.averagePrice>b.averagePrice;
}
int main(){
    int n;
    double d;        //n表示月饼的种类数，d表示当前的的市场需求量
    printf("请输入n(n<=1000),d(d<=500):");
    scanf("%d %lf",&n,&d);
 
    for(int i = 0;i<n;i++){
        scanf("%lf",&mCake[i].inventory);
    }
 
    for(int i = 0;i<n;i++){
        scanf("%lf",&mCake[i].totalPrice);
        mCake[i].averagePrice = mCake[i].totalPrice / mCake[i].inventory;
    }
 
    sort(mCake,mCake+n,cmp);        //将月饼按照从均价从高到低排序
    double revenue = 0;     //总收益
    for(int i = 0;i<n;i++){
        if(d >= mCake[i].inventory){
            d = d - mCake[i].inventory;
            revenue+=mCake[i].totalPrice;
        }else{      //剩余的市场需求量小于当前月饼的库存量，则满足市场需求量即可
            revenue += d * mCake[i].averagePrice;
            break;
        }
    }
    printf("%.2f\n",revenue);
    
    
    return 0;
}

给定数字0～9若干个，可以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小

例如给定两个0，两个1，三个5，一个8，最后得到的最小的数就是10015558

输入格式：每个输入包含一个用例，每个测试用例在一行中给出十个非负整数，顺序表示所拥有数字0，数字1，....数字9的个数

十个数字的总个数不超过50，且至少拥有一个非0数字

输出：在一行中输出所能够组成的最小的数

#include<stdio.h>
/*
    给定数字0～9若干个，可以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小
    例如给定两个0，两个1，三个5，一个8，最后得到的最小的数就是10015558
    输入格式：每个输入包含一个用例，每个测试用例在一行中给出十个非负整数，顺序表示所拥有数字0，数字1，....数字9的个数
    十个数字的总个数不超过50，且至少拥有一个非0数字
    
    输出：在一行中输出所能够组成的最小的数
*/
int num[2][10];     //第一行表示0～9的数字，第二行表示每个数字的个数
int main(){
    while(1){
        int count = 0;
        printf("请输入10个数字:");
        for(int i = 0;i<10;i++){
            scanf("%d",&num[1][i]);
            count += num[1][i];
        }
        if(count<=50 && num[1][0] != 50){   //十个数字的总个数不超过50，且至少拥有一个非0数字
            break;
        }else{
            printf("输入格式不规范！\n");
        }
    }
 
    //组最小的数，肯定是把本组数字中最小的数放在高位(保证高位不为0)，把较大的数放在低位
    int Minimal[55];
    int flag = 0;
    //先放高位
    for(int i = 1;i<10;i++){
        if(num[1][i] != 0){
            Minimal[flag++] = i;
            num[1][i]--;
            break;      //找到最高位放什么数字之后，跳出循环
        }
    }
 
    bool zeroExits = false;     //true:存在若干个0,false:不存在0
    if(num[1][0] != 0){
        zeroExits = true;
    }
 
    if(zeroExits == true){
        for(int i = 1;i<=num[1][0];i++){
            Minimal[flag++] = 0;
        }
        for(int i = 1;i<10;i++){
            if(num[1][i] != 0){     //这个数字没有被用尽，因为是从小到大的顺序，所以放到高位
                for(int j = 1;j<=num[1][i];j++){
                    Minimal[flag++] = i;
                }
            }
        }
    }else{      //不存在0
        for(int i = 1;i<10;i++){
            if(num[1][i] != 0){     //这个数字没有被用尽，因为是从小到大的顺序，所以放到高位
                for(int j = 1;j<=num[1][i];j++){
                    Minimal[flag++] = i;
                }
            }
        }
    }
 
    //输出
    for(int i = 0;i<flag;i++){
        printf("%d",Minimal[i]);
    }
    printf("\n");
    
    return 0;
}

给出N个开区间(x,y)，从中选择尽可能多的开区间，使得这些开区间两两没有交集

#include<stdio.h>
#include<algorithm>
using namespace std;
/*
    给出N个开区间(x,y)，从中选择尽可能多的开区间，使得这些开区间两两没有交集
*/
const int maxn = 110;
struct Interval{
    int x;
    int y;
}I[maxn];
 
bool cmp(Interval a,Interval b){
    if(a.x == b.x){
        return a.y<b.y;
    }else{
        return a.x>b.x;
    }
}
int main(){
    int n;      //代表区间的个数
    while (scanf("%d",&n),n != 0)
    {
        /* code */
        for(int i = 0;i<n;i++){
            scanf("%d%d",&I[i].x,&I[i].y);    //输入每个区间的左右端点值
        }
        sort(I,I+n,cmp);        //按照横坐标从大到小排列，横坐标相同时按纵坐标从小到大排列
        
        //ans记录当前不相交子区间的个数，lastX记录上一个被选中区间的左端点
        int ans = 1,lastX = I[0].x;
        for(int i = 1;i<n;i++){
            if(I[i].y <= lastX){    //如果该区间右端点在lastX左边
                ans++;      //不相交区间个数加1
                lastX = I[i].x;     //以I[i]作为新选中的区间
            }
        }
        printf("%d\n",ans);
    }
    
    return 0;
}