今天水来一天,就贴道水吧。。
原题>>https://www.luogu.org/problem/show?pid=2637<<
题目描述
因为奶牛们的节食运动(奶牛还节食?)给农夫JOHN余下了一大批干草无法处理,所以他准备要开一个拍卖会去出售他的干草。他有N(1<=N<=1000)批干草(每批大约100捆)。他的客户有M个(1<=M<=1000),都是和他相邻的农夫。 第I名农夫会告诉农夫JOHN他会为农夫JOHN的每批干草付P_i的钱(1<=P_i<=1,000,000)。每个农夫都想买(也只想买)农夫JOHN的一批草料。 为了确保农夫们不会互相嫉妒,所以农夫JOHN决定要以一个固定的价格出售他的草料。每一个出价比农夫JOHN的要价要高的农夫将会买到草料,余下的将会被拒绝购买:< 请你帮助农夫JOHN找出能让他赚到最多的钱的最低的单批草料的售价。
输入输出格式
输入格式:
- 第一行:两个被空格隔开的整数,N和M * 第二行到第M+1行:第I+1行只包含一个整数:P_i
输出格式:
第一行:由空格隔开的两个整数:农夫JOHN能出的每批草料的最低价格,以及他能赚到的最多的钱
输入输出样例
5 4 2 8 10 7
7 21
说明
输入样例解释:
农夫JOHN有5批草料,4个农夫想要购买。他们出价分别为:每批草料为2,8,10和7。
输出样例解释:
农夫JOHN应该把价格设定为7,这样会有3个农夫会付钱买草料,农夫JOHN自己会挣到21的钱。
这题我是在搜索里找到的。。但其实就是一道模拟水题呀。。
我的思路就是:先把出价有大到小排一下,然后依次定价,每一次降价刚好会多一个人购买。利润就是一个二次函数(开口向下)所以当找到递减趋势的时候直接打破就行,注意要用一个变量来标记定价哦~~~
#include<iostream> #include<algorithm> using namespace std; int cmp(int a,int b) { return a>b; } int main() { int n,m,a[1005]={0},mmax; int i,j,k,e=1,bj; cin>>n>>m; for(i=0;i<m;i++) { cin>>a[i]; } sort(a,a+m,cmp); k=a[0];mmax=a[0]; for(i=1;i<m;i++) { if(e>n) break; e++; k=a[i]*e; if(k>mmax) { mmax=k;bj=a[i]; } } cout<<bj<<" "<<mmax<<endl; }
今天的文章洛谷p2669_canoe上位机开发分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/48443.html