第一次,第二次,成交!

题目描述

因为奶牛们的节食运动(奶牛还节食?)给农夫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的钱。


贪心,卖给出价高的,sort排序。

只有N批草,如果M>N,只卖给后M人。然后枚举只有 i 个人买,因为有可能有人拖低单价。

枚举 i 个人时,尽量提高单价,即 a[ i ]。

#include <bits/stdc++.h>  
using namespace std;
int read()		//快读 
{
	int x;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
    return x;
}
int a[1005];
int main()
{
	int n=read(),m=read(),i,p,ans=0;
	for(i=1;i<=m;i++)
		cin>>a[i];
	//	a[i]=read();
	sort(a+1,a+1+m);
	for(i=max(1,m-n);i<=m;i++)	//枚举单价/人数 
		if(ans<a[i]*(m-i+1)){	//求最值 
			ans=a[i]*(m-i+1);	//人数*单价
			p=a[i];
		}
	printf("%d %d",p,ans);
    return 0;
}

 

上一篇:python多个变量赋值


下一篇:NodeType的三个属性值