首页 > 试题广场 >

搭配出售

[编程题]搭配出售

热度指数：3385 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

服装店新进了a条领带，b条裤子，c个帽子，d件衬衫，现在要把这些搭配起来售卖。有三种搭配方式，一条领带和一件衬衫，一条裤子和一件衬衫，一个帽子和一件衬衫。卖出一套领带加衬衫可以得到e元，卖出一套裤子加衬衫可以得到f元，卖出一套帽子加衬衫可以得到g元。现在你需要输出最大的获利方式

输入描述:

一行7个整数分别表示a,b,c,d,e,f,g。 $(1\leq a,b,c,d,e,f,g\leq 1e5)$

输出描述:

最大获利。

示例1

输入

2 3 4 5 6 7 8

输出

说明

4个帽子加4件衬衫获利32元，1条裤子加1件衬衫获利7元，一共得到39元。

算法知识视频讲解

pein531

贪心算法，先根据题中的三种搭配进行配对：(a, e), (b, f), (c, g)。原则就是先让衬衫去搭配领带、裤子和帽子中能使得收益更大的，按照收益排序，将这三个二元组放入到一个大根堆中，依次弹出堆顶元素计算总收益即可。记得每搭配完一次，衬衫数量d要做出相应的减少。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int a = Integer.parseInt(params[0]);
        int b = Integer.parseInt(params[1]);
        int c = Integer.parseInt(params[2]);
        int d = Integer.parseInt(params[3]);
        int e = Integer.parseInt(params[4]);
        int f = Integer.parseInt(params[5]);
        int g = Integer.parseInt(params[6]);
        // 将三种搭配放入一个大根堆中，按照三种搭配的获利对搭配进行降序排列
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        maxHeap.offer(new int[]{a, e});
        maxHeap.offer(new int[]{b, f});
        maxHeap.offer(new int[]{c, g});
        // 把衬衫分配给领带、裤子和帽子中赚钱多的
        long money = 0;
        while(!maxHeap.isEmpty() && d > 0){
            int[] temp = maxHeap.poll();
            money += (long)Math.min(temp[0], d) * temp[1];
            d -= temp[0];
        }
        System.out.println(money);
    }
}

编辑于 2021-03-06 13:18:45 回复(4)

我的兄弟叫高斯林

贪心思想

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int e = sc.nextInt();
        int f = sc.nextInt();
        int g = sc.nextInt();
        Queue<Mapping> mappings = new PriorityQueue<>(3);
        mappings.offer(new Mapping(a,e));
        mappings.offer(new Mapping(b,f));
        mappings.offer(new Mapping(c,g));
        int count = d;
        long max = 0;
        while(count > 0 && !mappings.isEmpty()){
            Mapping mapping = mappings.poll();
            if(count >= mapping.count){
                max += mapping.count * mapping.cost;
                count -= mapping.count;
            }else {
                max += count * mapping.cost;
                break;
            }
        }
        System.out.println(max);
    }
    private static class Mapping implements Comparable<Mapping>{
        long cost;
        int count;

        public Mapping(int count, long cost) {
            this.cost = cost;
            this.count = count;
        }

        @Override
        public int compareTo(Mapping o) {
            return (int)(o.cost - this.cost);
        }
    }
}

发表于 2021-03-05 16:52:06 回复(0)

牛客444127117号

按收益排个序，优先卖收益高的。

发表于 2022-03-17 11:02:35 回复(0)

牛客404270893号

$O(1)$ 贪心：在有限商品量的范围内，使用贪心选择最大价值的组合

a, b, c, d, e, f, g = map(int, input().split())
price = 0
for p, t in sorted([(e, 1), (f, 2), (g, 3)], reverse=True):
    if 1 == t:  # tie+shirt
        n = min(a, d)
        price += n * p
        a, d = a - n, d - n  # 剩余数量
        # print('tie+shirt', n, n * p)
    elif 2 == t:  # trousers+shirt
        n = min(b, d)
        price += n * p
        b, d = b - n, d - n  # 剩余数量
        # print('trousers+shirt', n, n * p)
    elif 3 == t:  # cap+shirt
        n = min(c, d)
        price += n * p
        c, d = c - n, d - n  # 剩余数量
        # print('cap+shirt', n, n * p)
print(price)

代码还可以简化，因为每个组合都是和衬衫，那么构建(price, type)组合就可以。

a, b, c, d, e, f, g = map(int, input().split())
price = 0
for p, t in sorted([(e, a), (f, b), (g, c)], reverse=True):
    n = min(t, d)
    price += n * p
    d -= n  # shirt剩余数量
print(price)

编辑于 2021-08-16 19:57:13 回复(0)

Lim0

贪心策略即可，首先要知道e,f,g三个的大小顺序，然后得知道各种对应的a,b,c的顺序。这里用到了unordered_map来实现。

在进行贪心选择时，首先选择价值最大的，保证d>0且当前选择的物件数量>0.按照从大到小顺序依次选择即可

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
int main(){
    int a,b,c,d,e,f,g;
    cin>>a;
    cin>>b;
    cin>>c;
    cin>>d;
    cin>>e;
    cin>>f;
    cin>>g;
    vector<int> price={e,f,g};
    sort(price.begin(),price.end());
    unordered_map<int,int> map={{e,a},{f,b},{g,c}};
    //贪心策略，优先选择最值钱的搭配卖
    long long profit=0;
    int min_p=price[0];
    int meadian_p=price[1];
    int max_p=price[2];
    while(d && map[max_p]){
        profit+=max_p;
        map[max_p]--;
        d--;
    }
    while(d && map[meadian_p]){
        profit+=meadian_p;
        map[meadian_p]--;
        d--;
    }
     while(d && map[min_p]){
        profit+=min_p;
        map[min_p]--;
        d--;
    }
    cout<<profit;
}

发表于 2021-04-03 20:43:12 回复(0)

牛客972211156号

s = list(map(int, input().split()))
a, b, c, d, e, f, g = s
# a, b, c, d, e, f, g = 2,3,4,5,6,7,8
info = [(a,e),(b,f),(c,g)]
info = sorted(info, key=lambda x: x[1], reverse=True)
benefit = 0
remaining = d
for i in range(3):
    if remaining==0:
        break
    num = min(info[i][0],remaining)
    benefit += num*info[i][1]
    remaining -= num
print (benefit)

发表于 2021-03-18 11:35:16 回复(1)

C/C++

牛客104264849号

c++ ：原来用int会超过长度导致溢出

#include<bits/stdc++.h>

using namespace std;
int main() {
long long a,b,c,d,e,f,g;
cin >>a >>b >>c >>d >>e >>f >>g ;
if (e > g) {
swap(e,g);
swap(a,c);
}
if (f > g) {
swap(f, g);
swap(b, c);
}
if (e > f) {
swap(e, f);
swap(a, b);
}
long long ans = 0;
while (d > 0 && a > 0) {
if (c > 0) {
ans += min(d,c)*g;
d -= c;
c = 0;
} else if (b > 0) {
ans += min(b,d)*f;
d -= b;
b = 0;
} else if (a > 0) {
ans += min(a,d)*e;
d -= a;
a = 0;
}
}
cout << ans << endl;
return 0;
}

发表于 2022-03-12 14:21:58 回复(1)

Java

苏觅云

import java.util.*;
public class Main {
    public static long cal(long d, long a, long e, long b, long f, long c, long g) {
        long cnt = 0;
        long minAd = Math.min(a, d);
        cnt += (minAd * e);
        a -= minAd;
        d -= minAd;
        long minBd = Math.min(b, d);
        cnt += (minBd * f);
        b -= minBd;
        d -= minBd;
        long minCd = Math.min(c, d);
        cnt += (minCd * g);
        c -= minCd;
        d -= minCd;
        return cnt;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int e = sc.nextInt();
        int f = sc.nextInt();
        int g = sc.nextInt();
        long[] arr = new long[6];
        arr[0] = cal(d, a, e, b, f, c, g);
        arr[1] = cal(d, a, e, c, g, b, f);
        arr[2] = cal(d, b, f, a, e, c, g);
        arr[3] = cal(d, b, f, c, g, a, e);
        arr[4] = cal(d, c, g, a, e, b, f);
        arr[5] = cal(d, c, g, b, f, a, e);
        Arrays.sort(arr);
        System.out.println(arr[5]);
    }
}

发表于 2022-06-23 15:31:54 回复(0)

卷__

贪心，得用long存储，不然溢出

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
        long a, b, c, d, e, f, g;
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        d = sc.nextInt();
        e = sc.nextInt();
        f = sc.nextInt();
        g = sc.nextInt();
        long sum = 0;
        if (d == 0) {
            System.out.println(0);
        } else {
            long tem = d;
            while (tem > 0) {
                if (g == f && f == e || (g==0 && f==e) || (f==0 && g==e) || (e==0 && g==f)) {
                    if (a > b && a > c) {
                        if (a >= tem) {
                            a = tem;
                            sum += a * g;
                            tem = 0;
                            a=0;
                        } else {
                            sum += a * g;
                            tem -= a;
                            a=0;
                        }
                    } else if (b > a && b > c) {
                        if (b >= tem) {
                            b = tem;
                            sum += b * g;
                            tem = 0;
                            b=0;
                        } else {
                            sum += b * g;
                            tem -= b;
                            b=0;
                        }
                    } else if (c > a && c > b) {
                        if (c >= tem) {
                            c = tem;
                            sum += c * g;
                            tem = 0;
                            c=0;
                        } else {
                            sum += c * g;
                            tem -= c;
                            c=0;
                        }
                    }
                } else if (g > f && g > e) {
                    if (c >= tem) {
                        c = tem;
                        sum += c * g;
                        tem = 0;
                        c=0;
                        g = 0;
                    } else {
                        sum += c * g;
                        tem -= c;
                        c=0;
                        g=0;
                    }
                } else if (f > g && f > e) {
                    if (b >= tem) {
                        b = tem;
                        sum += b * f;
                        tem = 0;
                        b=0;
                        f = 0;
                    } else {
                        sum += b * f;
                        tem -= b;
                        b=0;
                        f=0;
                    }
                } else if (e > g && e > f) {
                    if (a >= tem) {
                        a = tem;
                        sum += a * e;
                        tem = 0;
                        a=0;
                        e = 0;
                    } else {
                        sum += a * e;
                        tem -= a;
                        a=0;
                        e=0;
                    }
                }

                if(a==0 && b==0 && c==0){
                    break;
                }
            }
            System.out.println(sum);
        }
    }
}

发表于 2022-04-14 00:14:29 回复(0)

牛客744407822号

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int[][] arr = new int[3][2];
        arr[0][0] = scanner.nextInt();
        arr[1][0] = scanner.nextInt();
        arr[2][0] = scanner.nextInt();
        int d = scanner.nextInt();
        arr[0][1] = scanner.nextInt();
        arr[1][1] = scanner.nextInt();
        arr[2][1] = scanner.nextInt();
        long res = 0;
        while (d>0){
            int i = find(arr);
            if (i!=-1){
                if (arr[i][0]>d){
                    res += (long)arr[i][1]*d;
                    d=0;
                }else {
                    res += (long)arr[i][1]*arr[i][0];
                    d = d-arr[i][0];
                    arr[i][0]=0;
                }
            }else {
                break;
            }
        }
        System.out.println(res);
    }

    private static int find(int[][] arr) {
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[res][0]==0){
                res = i;
            }else if (arr[i][0]!=0&&arr[i][1]>=arr[res][1]){
                res = i;
            }
        }
        return arr[res][0]==0?-1:res;
    }
}

发表于 2021-09-24 23:30:56 回复(0)

爱看电影的小男孩

import java.util.Scanner;

/*
   大整数问题
*/
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[] arr = new long[7];
        for(int i=0;i<7;i++){
            arr[i] = sc.nextInt();
        }

        long sum = 0L;
        while (arr[3]>0){
            int index = -1;
            long max01 = 0;
            for(int i=4;i<7;i++){
                if(arr[i]>max01){
                    max01 = arr[i];
                    index = i;
                }

            }
            if(max01 == 0)
                break;
            if(arr[3]>arr[index-4]){
                arr[3] = arr[3] - arr[index-4];
                sum = arr[index-4]*max01+sum;
                arr[index] = 0;
            }else{
                sum = arr[3]*max01+sum;
                arr[3] = 0;

            }
        }
        System.out.println(sum);
    }
}

发表于 2021-09-21 10:41:22 回复(0)

JCoder

简单点，AC的方式简单点

a = list(map(int, input().split()))
b = [(a[4], a[0]), (a[5], a[1]), (a[6], a[2])]
b.sort()
ans = 0
for i in range(2, -1, -1):
    ans += min(a[3], b[i][1]) * b[i][0]
    a[3] = max(0, a[3] - b[i][1])
print(ans)

编辑于 2021-09-02 13:03:31 回复(2)

李洞宾

**居然卡数据范围，原来是没加long，一直卡百分之40

发表于 2021-08-27 13:37:30 回复(0)

牛客474721145号

有人遇到数据溢出的问题吗

发表于 2021-08-18 18:52:28 回复(0)

y_ss

这题只要找出最大值的数量，从最大值的数量开始减即可，可以直接运算，这题考的，是大数。

发表于 2021-08-14 18:35:25 回复(0)

牛客133059086号

import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.next();
if(s.length()==0){
System.out.println(0);
}
int[] a = new int[n];
a[0] = s.charAt(0)=='E'?1:-1;
int max = a[0];
for(int i=1;i<n;i++){
if(s.charAt(i)=='E'){
a[i] = Math.max(1,a[i-1]+1);
}else{
a[i] = Math.max(-1,a[i-1]-1);
}
max = Math.max(max,a[i]);
}
if(max>0){
System.out.println(max);
}else{
System.out.println(0);
}
}
}

编辑于 2021-08-05 21:36:27 回复(0)

许愿给我来一个offer呀

贪心思想，尽可能选利益最大的

importjava.util.*;

publicclassMain{

publicstaticvoidmain(String[]args){

Scanner sc =newScanner(System.in);

longa = sc.nextInt();

longb = sc.nextInt();

longc = sc.nextInt();

longd = sc.nextInt();

longe = sc.nextInt();

longf = sc.nextInt();

longg = sc.nextInt();

longmax =Math.max(Math.max(e,f),Math.max(e,g));

longcount =0;

longsecond =0;

longsecond_max=0;

longthird =0;

if(max==g){

count = c;

if(f<e){

second_max = e;

second = a;

third =b;

}else{

second_max = f;

second = b;

third =a;

}

}elseif(max==f){

count = b;

if(g<e){

second_max = e;

second = a;

third =c;

}else{

second_max = g;

second = c;

third = a;

}

}else{

count = a;

if(g<f){

second_max = f;

second = b;

third = c;

}else{

second_max = g;

second = c;

third = b;

}

String result ="";

if(d-count<=0){

result =String.valueOf( max*d);

}elseif(d-count>0&&d-count<second){

result =String.valueOf(max*count+second_max*(d-count)) ;

}elseif(d>(count+second)&&d-count-second<third){

result = String.valueOf(max*count +second_max*second+(d-count-second)*third);

}else{

result =String.valueOf( a*e+f*b+g*c);

}

System.out.print(result);

}

发表于 2021-05-07 10:38:10 回复(0)

牛客默克尔号

l=[int(i) for i in input().split()]
ll=[]
for i in range(3):
    ll.append([l[i],l[i+4]])
ll.append([l[3],0])
ll.sort(key=lambda x: x[1],reverse=True)
sum=0
p=0
for i in range(3):
    if ll[i][0]>ll[3][0]:
        sum+=ll[3][0]*ll[i][1]
        print(sum)
        p=1
        break
    else:
        sum+=ll[i][0]*ll[i][1]
        ll[3][0]-=ll[i][0]
if p==0:
    print(sum)

发表于 2021-04-14 19:47:16 回复(0)

Python

梦飞翔201909251511348

L = list(map(int,input().split()))
p=sorted([L[i] for i in range(4,7)],reverse=True)
profit=0
for i in range(3):
c=min(L[L.index(p[i])-4],L[3])
profit+=p[i]*c
if c==L[3]:
break
L[3]-=c

print(profit)

发表于 2021-04-03 17:29:08 回复(0)

REFFO倒了

贪心算法

li = list(map(int,input().split()))
b=sorted([li[i] for i in range(4,7)],reverse=True)
out=0
for i in range(3):
    c=min(li[li.index(b[i])-4],li[3])
    out+=b[i]*c
    if c==li[3]:
       break
    li[3]-=c        
print(out)

发表于 2021-03-12 10:52:18 回复(0)