首页 > 其他分享 >洛谷 P1208混合牛奶 题解

洛谷 P1208混合牛奶 题解

时间:2023-01-26 15:22:57浏览次数:43  
标签:洛谷 牛奶 weight int 题解 price 单价 P1208 sum

一道贪心算法不是很明显的题目,其实一般的递推也可以做。


 

大体思路:肯定优先购买单价最低的奶农的牛奶,那么就需要先根据牛奶单价进行排序,这里用结构体会更好一点。之后在从前往后一个一个枚举,直至购买的牛奶数量达到要求即可。

话不多说,上代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long n,m,sum;
 4 struct farm{
 5     int price,weight;
 6 }a[100001];//结构体,price表示单价,weight表示可出售的质量 
 7 bool cmp(farm x,farm y){
 8     return x.price<y.price;
 9 }//根据牛奶的单价进行排序 
10 int main(){
11     cin>>n>>m;
12     for(int i=1;i<=m;i++){
13         cin>>a[i].price>>a[i].weight;
14     }//输入 
15     sort(a+1,a+m+1,cmp);//根据上面的要求进行排序 
16     for(int i=1;i<=m;i++){
17         if(a[i].weight>n){//可出售质量超出剩余需求 
18             sum+=n*a[i].price;//总和+=剩余需求*单价 
19             break;//结束循环 
20         }
21         n-=a[i].weight;//剩余需求减去牛奶数量 
22         sum+=a[i].price*a[i].weight; //总和+=单价*所有的质量 
23     }
24     printf("%d",sum);
25     return 0;
26 }

 

标签:洛谷,牛奶,weight,int,题解,price,单价,P1208,sum
From: https://www.cnblogs.com/zhangqixun/p/17067843.html

相关文章

  • CF1780 F.Three Chairs - 题解
    给定数列\(\{a_n\}\),求无序三元组\((i,j,k)\)的数量,满足\(\gcd(\min(a_i,a_j,a_k),\max(a_i,a_j,a_k))=1\),\(n\leq3\cdot10^5,a_i\leq3\cdot10^......
  • ajax跨域访问的问题解决
    在web项目中经常用到在ajax中进行跨域访问,比如在a域中访问b域中的服务,却实现不了。原因是:浏览器为了保证服务器数据的安全,对于这种请求,所给予的权限是较低的,通常只允许调用......
  • 题解 CF1780G【Delicious Dessert】
    SAM板子题。在P3804【模板】后缀自动机(SAM)中,我们已经会求每个等价类(SAM状态)在原串中的出现次数。本题中,我们需要求所有长度能被出现次数整除的子串。我们知道一......
  • CF850F 题解
    题意传送门有一袋\(n\)个颜色球,第\(i\)个颜色的球有\(a_i\)个。当袋子里至少有两个不同颜色的球时,执行以下步骤:一个接一个的按照顺序随机取出两个的球,这些球......
  • 安装OpenCV时提示缺少boostdesc_bgm.i文件的问题解决方案
    安装OpenCV时,会遇到下面的错误/home/zhang/slam/opencv-3.4.5/opencv_contrib/modules/xfeatures2d/src/boostdesc.cpp:653:20:fatalerror:boostdesc_bgm.i:没有那个文......
  • LeetCode-343. 整数拆分 - 题解分析
    题目来源343.整数拆分题目详情给定一个正整数 n ,将其拆分为k个正整数的和( k>=2 ),并使这些整数的乘积最大化。返回你可以获得的最大乘积 。示例1:输入:......
  • 题解 CF1773H【Hot and Cold】
    赛时跟队友一起摆烂了,于是没做出来,回来补题。如果询问到了答案,可以直接判断并退出,因此下文的询问过程并没有考虑这一点。显然“\((1,1)\)比\((0,0)\)离所求位置更近”......
  • 关于gnome-control-center的问题解决
    突然发现电脑桌面的设置无法打开,点击后一直转圈。在网上研究了一圈,发现可能是gnome出了问题,输入指令gnome-control-center,结果报了如下错误:gnome-control-center:......
  • 洛谷 P1478 陶陶摘苹果(升级版) 题解
    这道题只要会自定义cmp恰当地进行排序,其他部分没有什么大问题。上代码:1#include<bits/stdc++.h>2usingnamespacestd;3intn,s,h1,h2,cnt;4structapple{......
  • CF Educational Round 142 (Rated for div2) 题解
    A注意到除了血量为\(1\)的怪物,其余的怪物直接斩杀是更合理的。所以只要统计血量为\(1\)的怪物的个数即可。#include<cstdio>voidsolve(){ intn;scanf("%d",......