Edoardo possiede un ristorante per al massimo N persone. L’entrata del ristorante ha un guardaroba con N appendini. Ogni cliente può usare un appendino del guardaroba per metterci le proprie giacche. Utilizzare l’iesimo gancio ha un costo ai in euro. Ogni persona può utilizzare al massimo un gancio.
Stasera Edoardo si aspetta di ricevere M clienti al ristorante. Naturalmente ogni cliente vorrà utilizzare gli appendini con il costo minimo (se ce ne sono di più con lo stesso costo, ne prenderà uno a caso tra questi). Purtroppo, se nel momento in cui un cliente arriva non ci sono appendini disponibili, Edoardo deve pagare una multa di D euro al cliente.
Aiuta Edoardo a trovare il profitto in euro (può anche essere negativo) che avrà questa sera per quanto riguarda il guardaroba. Puoi assumere che prima che i clienti arrivino tutti gli appendini siano disponibili e che nessun altro a parte gli m clienti visiterà il ristorante.
Input
Il programma deve leggere da un file di nome “input.cxt”. La prima riga contiene due interi N e D.
La riga successiva contiene N interi, cioè a1, a2, …, aN. La terza riga contiene l’intero M.
Output
Il programma deve stampare sul file la risposta al problema.
Assunzioni
1 ≤ N ≤ 100.000
1 ≤ M ≤ 200.000
1 ≤ ai ≤ 1000
1 ≤ D ≤ 2000
Esempio
input output
2 1 -5
2 1
1 0
Ordinati i prezzi in ordine crescente li prendiamo tutti in ordine, finiti sottraiamo al profitto la multa:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <cstdlib> #include <iostream> #include<fstream> #include<algorithm> using namespace std; ifstream in; ofstream out; int n,d,m,profitto; int main() { in.open("input.txt"); out.open("output.txt"); in >> n>>d; int prezzi[n]; for (int i=0;i<n;i++) in>>prezzi[i]; in>>m; profitto=0; sort(prezzi,prezzi+n); for (int i=0;i<m;i++) if(i<n) profitto+=prezzi[i]; else profitto-=d; out<<profitto; return 0; } |
