笔试刷题-滴滴2018-06-13

题目描述：

/**
某餐馆有n张桌子，每张桌子有一个参数：
a 可容纳的最大人数；
有m批客人，每批客人有两个参数:b人数，c预计消费金额。
在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大

输入描述:
输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000)
 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。
 接下来m行，每行两个参数b,c。
 分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。


输出描述:
输出一个整数,表示最大的总预计消费金额

输入例子1:
3 5
2 4 2
1 3
3 5
3 7
5 9
1 10

输出例子1:
20
*/ 

思路如下：

最大堆+排序
客户按照人数也是升序排列
大顶堆为Node节点按照消费大的在顶放，消费额度相同人数少优先，初始为空
先把桌子按照可容纳的人数升序排列并且升序遍历

把当前该桌子能容纳的Node都扔到大顶堆中，然后给其分配即可

代码如下：

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

#define MAX_N 50005
#define MAX_M 50005

using namespace std;

struct Node
{
    int numOfClient=-1, cost=-1;
    Node() {}
    Node(int numOfClient, int cost)
    {
        this->numOfClient=numOfClient;
        this->cost=cost;
    }
    Node(const Node& node)
    {
        this->numOfClient=node.numOfClient;
        this->cost=node.cost;
    }
};

//若消费相同，人少优先
//注意这里大小于号有点不自然
struct NodeCmpByCostStruct
{
    bool operator () (const Node& node1, const Node& node2)
    {
        if(node1.cost==node2.cost)
            return node1.numOfClient>node2.numOfClient;
        return node1.cost<node2.cost;
    }
};

bool NodeCmpByNumOfClient(const Node& node1, const Node& node2)
{
    return node1.numOfClient<node2.numOfClient;
}

struct Table
{
    int cap=-1;
    Table() {}
    Table(int cap)
    {
        this->cap=cap;
    }
    Table(const Table& table)
    {
        this->cap=table.cap;
    }
};

bool TableCmpByCap(const Table& table1, const Table& table2){
    return table1.cap<table2.cap;
}

Table tables[MAX_N];
Node nodes[MAX_M];

int main()
{
    int N, M;
    long long sum=0;
    scanf("%d%d", &N, &M);
    for(int i=0; i<N; i++){
        int cap;
        scanf("%d", &cap);
        tables[i]=Table(cap);
    }
    for(int i=0; i<M; i++){
        int numOfClient, cost;
        scanf("%d%d", &numOfClient, &cost);
        nodes[i]=Node(numOfClient, cost);
    }
    //桌子按照容量升序排序
    sort(tables, tables+N, TableCmpByCap);
    //节点按人数升序排序
    sort(nodes, nodes+M, NodeCmpByNumOfClient);
    //构造消费优先队列（大顶堆）
    priority_queue<Node, vector<Node>, NodeCmpByCostStruct> pque;

//    for(int i=0; i<M; i++){
//        pque.push(nodes[i]);
//    }
//    while(!pque.empty()){
//        Node node=pque.top();
//        pque.pop();
//        printf("%d %d\n", node.numOfClient, node.cost);
//    }

    int i=0, j=0;
    while(i<N){
        while(j<M && nodes[j].numOfClient<=tables[i].cap){
            pque.push(nodes[j]);
            j++;
        }
        if(pque.empty()){
            i++;
            continue;
        }
        Node node=pque.top();
        pque.pop();
        sum+=(long long)node.cost;
        i++;
    }
    printf("%lld", sum);
    return 0;
}