[アルゴリズム]オンライン販売BOJ 1246

[BOJ]1246开线销售巧克力

📍 質問する

慶来は鶏を飼っていたが、今年の冬の卵の豊作は腹を抱えて笑った.そしてこれらの卵を栄養卵に偽装し、オークションに売るつもりだ.
慶来にはN個の卵があり、潜在的な顧客はM人だ.また、iのお客様は、誰もがPi価格以下で卵を買うことができると話しています.
庆来は栄养卵なので、だまされたという罪悪感から、1人の客に2个以上の卵を売らないことにした.しかし、上記の規定では、収益を最大値に引き上げたいため、いくら売るかを検討している.つまり、A価格で卵を販売すると、PiがA価格以上のお客様全員が卵を購入します.(もちろん卵の総数量を超えて販売することはできません)
問題は、卵の最低価格をどのように確定し、最大収益を実現するかです.

📍 入力

1行目には整数N(1≦N≦1000)とM(1≦M≦1000)が入力される.2行目からM+1行目まで、i+1行はPi(1≦Pi≦1000000)を入力する.

📍 しゅつりょく

1行目は慶来が設定した価格とこの価格で上がることができる収益を出力します.

📍 に答える

ハーモニー

from sys import stdin
N, M = map(int,stdin.readline().split())
prices = [] # 가격 값들
total = 0 # 총 판매 값
for _ in range(M):
  prices.append(int(stdin.readline()))
prices.sort(reverse=True) # 가격 값들 내림차순으로 정렬
for i in range(M):
  num = N # 달걀의 수
  # 만약 달걀의 가격에 팔 수 있는 사람의 수가 전체 달걀의 수보다 적다면
  if i + 1 < N:
    num = i + 1 # 판매 가능한 달걀의 수 갱신
  tmp = prices[i] * num # 현재 달걀의 가격 * 판매 가능한 달걀의 수
  if total < tmp:
    price = prices[i]
    total = tmp;
print(price, total)