P2637 第一次，第二次，成交！

题目描述

因为奶牛们的节食运动（奶牛还节食？）给农夫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能出的每批草料的最低价格，以及他能赚到的最多的钱

输入输出样例

输入样例#1：复制

输出样例#1：复制

7 21

说明

输入样例解释：

农夫JOHN有5批草料，4个农夫想要购买。他们出价分别为：每批草料为2，8，10和7。

输出样例解释：

农夫JOHN应该把价格设定为7，这样会有3个农夫会付钱买草料，农夫JOHN自己会挣到21的钱。

/*
    要让john卖更多的钱。
    我们把每个农夫出的钱降序排序。
    枚举每个农夫 i=1 -> m ,
    那么i和i之前的农夫 1->i 都可以用p[i]的价格买到草料，
    所以 ans=max(ans,p[i]*min(i,n))，
    为什么要写min(i,n)，
    是因为 可能会出现草料比农夫多的情况，
    但是最多只会有n个农夫来买草料，多余的(m-n)批草料是不会有人买的。
    所以，我们也可以直接让i枚举到min(n,m)
        然后让ans=max(ans,p[i]*i)就行了。 
*/ 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e3+5;

int n,m;
int p[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d",&p[i]);
    sort(p+1,p+m+1,greater<int>() );
    int ans_sum=0,ans_min=0;
//  for(int i=1;i<=m;++i)
//  {
//      if(ans_sum<p[i]*min(i,n))
//      {
//          ans_sum=p[i]*min(i,n);
//          ans_min=p[i];
//      }
//  }
    for(int i=1;i<=min(n,m);++i) //也可以这样写，直接枚举到min(人，草) 
    {
        if(ans_sum<p[i]*i)
        {
            ans_sum=p[i]*i;
            ans_min=p[i];
        }
    }
    printf("%d %d",ans_min,ans_sum);
    return 0;
}