CodeForces 416C
14812 단어 CodeForces
description:
Innovation technologies are on a victorious march around the planet. They integrate into all spheres of human activity! A restaurant called “Dijkstra’s Place” has started thinking about optimizing the booking system. There are n booking requests received by now. Each request is characterized by two numbers: ci and pi — the size of the group of visitors who will come via this request and the total sum of money they will spend in the restaurant, correspondingly. We know that for each request, all ci people want to sit at the same table and are going to spend the whole evening in the restaurant, from the opening moment at 18:00 to the closing moment. Unfortunately, there only are k tables in the restaurant. For each table, we know ri — the maximum number of people who can sit at it. A table can have only people from the same group sitting at it. If you cannot find a large enough table for the whole group, then all visitors leave and naturally, pay nothing. Your task is: given the tables and the requests, decide which requests to accept and which requests to decline so that the money paid by the happy and full visitors was maximum.
Input:
The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of requests from visitors. Then n lines follow. Each line contains two integers: ci, pi (1 ≤ ci, pi ≤ 1000) — the size of the group of visitors who will come by the i-th request and the total sum of money they will pay when they visit the restaurant, correspondingly. The next line contains integer k (1 ≤ k ≤ 1000) — the number of tables in the restaurant. The last line contains k space-separated integers: r1, r2, …, rk (1 ≤ ri ≤ 1000) — the maximum number of people that can sit at each table.
Output:
In the first line print two integers: m, s — the number of accepted requests and the total money you get from these requests, correspondingly. Then print m lines — each line must contain two space-separated integers: the number of the accepted request and the number of the table to seat people who come via this request. The requests and the tables are consecutively numbered starting from 1 in the order in which they are given in the input.
If there are multiple optimal answers, print any of them.
Examples:
Input 3 10 50 2 100 5 30 3 4 6 9 Output 2 130 2 1 3 2
제목의 대의: 한 식당에 k개의 테이블이 있고 i번째 테이블은 최대 리 사람이 앉을 수 있다.현재 n단 고객이 왔습니다. i단 고객은 모두 Ci 개인이 있어서 수익을 가져올 것입니다.모든 테이블은 한 무리의 고객만 배치할 수 있을 뿐만 아니라, 한 무리의 고객도 한 테이블에 앉아야 한다.몇 명의 고객을 받아들이고 몇 개의 테이블에 배치하면 가장 큰 수익을 얻을 수 있느냐고 물었다.
문제 풀이 사고방식: 1.분명히 고객의 요구에 따라 한 무리의 고객들은 수용량이 인원수보다 많은 탁자를 찾는다.그리고 테이블 하나는 한 무리의 고객에게만 사용할 수 있다.그럼 욕심 전략의 요구를 충족시키는 거야.테이블의 수량이 제한되어 있기 때문에 먼저 고객군을 수익의 높낮이에 따라 순서대로 배치하면 최대 수익을 얻을 수 있다.2. 마지막 결과는 수용할 수 있는 고객군의 수량과 총 수익을 출력해야 할 뿐만 아니라 입력한 순서에 따라 수용할 수 있는 고객의 순서와 대응하는 테이블 번호를 순서대로 제시해야 하기 때문이다.그래서 입력할 때 입력 순서를 기록해야 한다.3. multiset으로 테이블의 상태를 보존하고 고객군에 테이블을 설치한다id는 분배에 대응하는 책상 id를 표시하며, 받아들이지 않으면 -1로 분배한다.정렬이 끝난 후 고객의 수를 차례대로 읽고 멀티셋에서 앉을 수 있는 가장 작은 테이블을 찾습니다.찾지 못하거나 책상이 없으면 -1로 돌아갑니다.
소스 코드:
#include1005];
multiset t;
set
::iterator it;
int sum = 0,acc=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
a[i].id = i;
scanf("%d%d",&a[i].c,&a[i].p);
}
scanf("%d",&k);
table temp;
for(int i=1;i<=k;i++){
temp.id = i;
scanf("%d",&temp.num);
t.insert(temp);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
temp.num = a[i].c;
it = t.lower_bound(temp);
if(it==t.end()){
a[i].table_id = -1;
}else{
a[i].table_id = (*it).id;
t.erase(it);
sum+=a[i].p;
acc++;
}
}
printf("%d %d
",acc,sum);
sort(a+1,a+1+n,comp);
for(int i=1;i<=n;i++){
if(a[i].table_id!=-1)
printf("%d %d
",i,a[i].table_id);
}
return0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
문제 풀이 보고서 의 CodeForces 91B QueueOtherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest fro...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
