L2-003. 月饼 排序&贪心。PAT L2-003问题解答。

L2-003. 月饼

时限制

100 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

月饼是神州人于中秋佳节时吃的相同种民俗食物,不同地段有许多不同风味的月饼。现被得有品类月饼的库存量、总售价、以及市场的绝酷需求量,请而算好得的极其充分收入是稍稍。

在意:销售时许取出一些库存。样例给有底情况是如此的:假如我们发3种月饼,其库存量分别吗18、15、10万吨,总售价分别吗75、72、45亿冠。如果市场的绝要命需求量只发生20万吨,那么我们太可怜收益策略应该是卖出所有15万吨第2种月饼、以及5万吨第3栽月饼,获得
72 + 45/2 = 94.5(亿首届)。

输入格式:

每个输入包含1只测试用例。每个测试用例先为来一个未跳1000底正整数N表示月饼的类数、以及非超过500(以万吨为单位)的正整数D表示市场最特别需求量。随后同实践被出N个正数表示每种月饼的库存量(以万吨为单位);最后一行给出N个正数表示每种月饼的究竟售价(以亿首位吗单位)。数字中坐空格分隔。

输出格式:

对每组测试用例,在一行中输出最特别收入,以亿初呢单位并精确到有些数点后2位。

输入样例:

3 20
18 15 10
75 72 45

输出样例:

94.50

#include <bits/stdc++.h>

#define INF 0x3fffffff
#define eps 1e-8

typedef long long LL;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int maxn = 1000+5;
using namespace std;

int num[maxn];
int val[maxn];

struct Food {
double num;
double val;
double v;
}f[maxn];

bool cmp(Food f1,Food f2) {
    return f1.v > f2.v;
}
int main() {
    //freopen("in.txt","r",stdin);
    int n,d;
    cin>>n>>d;
    for(int i = 0; i < n; i++)
        cin>>f[i].num;
    for(int i = 0; i < n; i++) {
        cin>>f[i].val;
        f[i].v = f[i].val/f[i].num;
    }

    sort(f,f+n,cmp);
    double sum = 0;

        for(int i = 0; i < n; i++) {
            if(d>=f[i].num){
                sum += f[i].val;
                d -= f[i].num;
            }
            else{
                sum += d*f[i].v;
                break;
            }
        }
        printf("%.2f\n",sum);
    return 0;
}

PAT
L2-003题材解答
:月饼是炎黄口以中秋佳节时吃的平栽传统食品,不同地区发生成百上千不比风味的月饼。现吃一定有类型月饼的库存量、总售价、以及市场的极端可怜需求量,请你算好赢得的卓绝深收益是聊。

专注:销售时许取出一些库存。样例给出的图景是这么的:假如我们来3栽月饼,其库存量分别吗18、15、10万吨,总售价分别吗75、72、45亿首位。如果市场之极端深需求量只来20万吨,那么我们最特别收入策略应该是卖出所有15万吨第2栽月饼、以及5万吨第3种植月饼,获得
72 + 45/2 = 94.5(亿长)。

输入格式:

每个输入包含1单测试用例。每个测试用例先被起一个免超过1000的正整数N表示月饼的色数、以及不跳500(以万吨为单位)的正整数D表示市场最为深需求量。随后同执行于出N个正数表示每种月饼的库存量(以万吨为单位);最后一执吃出N个正数表示每种月饼的总售价(以亿处女吧单位)。数字中为空格分隔。

输出必威官网格式:

针对每组测试用例,在一行中输出最老收入,以亿首届啊单位并规范到稍微数点后2各。

输入样例:

3 20

18 15 10

75 72 45

出口样例:

94.50

自道是开是L2中极次之题了,除了代码量有硌好,其他类从没什么问题了。

一直上代码。

//

//  main.cpp

//  L2-03

//

//  Created by MaLker on 2017/3/13.

//  Copyright © 2017年 MaLker. All rights reserved.

//



#include 

#include 

using namespace std;

struct moon{

    double mess;

    double pries;

    //最大收益

    double ave;

}a[1005];

int main(int argc, const char * argv[]) {

    int n,ned;//ned 实际为need,即需求

    while (scanf("%d%d",&n,&ned)!=EOF) {

        for (int i=0; i

 

相关文章