餐馆

C++ 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2017-06-09

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

struct guest {
	int num;
	int money;
};
bool cmp(guest a, guest b) {
	if (a.money == b.money) {
		return a.num < b.num;
	}
	return a.money > b.money;
}
int main() {
	using namespace std;
	int n, m;
	while (cin >> n >> m) {
		multiset<int> desk;
		vector<guest> people(m);
		long long ans = 0;
		for (int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			desk.insert(temp);
		}
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			people[i].num = a;
			people[i].money = b;
		}
		sort(people.begin(), people.end(), cmp);
		for (int i = 0; i < m; i++) {
			if (desk.empty()) {
				break;
			}
			if (people[i].num <= *desk.rbegin()) {
				ans += people[i].money;
				desk.erase(desk.lower_bound(people[i].num));
			}
		}
		cout << ans << endl;
	}
	return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2017-06-11

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
 
struct guest {
    int num;
    int money;
};
bool cmp(guest a, guest b) {
    if (a.money == b.money) {
        return a.num < b.num;
    }
    return a.money > b.money;
}
int main() {
    using namespace std;
    int n, m;
    while (cin >> n >> m) {
        multiset<int> desk;
        vector<guest> people(m);
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            int temp;
            cin >> temp;
            desk.insert(temp);
        }
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            people[i].num = a;
            people[i].money = b;
        }
        sort(people.begin(), people.end(), cmp);
        for (int i = 0; i < m; i++) {
            if (desk.empty()) {
                break;
            }
            if (people[i].num <= *desk.rbegin()) {
                ans += people[i].money;
                desk.erase(desk.lower_bound(people[i].num));
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C++ 解法, 执行用时: 10ms, 内存消耗: 8840KB, 提交时间: 2017-02-03

/*
 * 餐馆
 * 某餐馆有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范围内。
 */

#include <iostream>
#include <set>
#include <algorithm>
#include <stdio.h>

using namespace std;

struct Customer {
    int num;
    int cost;
};

int compare(const Customer a, const Customer b) {
    return a.cost == b.cost ? a.num < b.num : a.cost > b.cost;
}

long long int GetMaxValue(int n, int m) {
    Customer * c = new Customer[m];
    multiset<int> s;

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        s.insert(x);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &c[i].num, &c[i].cost);

    }
    sort(c, c + m, compare);

    long long int res = 0;

    for (int i = 0; i < m; i++) {
        set<int>::iterator it = s.lower_bound(c[i].num);
        if (it != s.end()) {
            res += c[i].cost;
            s.erase(it);
        }
    }

    delete [] c;

    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    printf("%lld\n", GetMaxValue(n, m));
    return 0;
}

C++ 解法, 执行用时: 10ms, 内存消耗: 8848KB, 提交时间: 2017-02-24

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int m, n;
vector<int> capacity;
struct Guest
{
	int num, cost;
	Guest(int n, int c) :num(n), cost(c) {}
};
bool operator<(const Guest & a, const Guest & b)
{
	if (a.cost>b.cost)
	{
		return true;
	}
	else if (a.cost<b.cost)
	{
		return false;
	}
	else return a.num < b.num;
}
vector<Guest> guests;
int main()
{
	scanf("%d %d", &n, &m);
//	printf("%d %d\n", n, m);
	capacity.reserve(n);
	guests.reserve(m);
	for (size_t i = 0; i < n; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		capacity.push_back(tmp);
	//	printf("capacity[%d]=%d\n", i, capacity.back());
	}
	
	for (size_t i = 0; i < m; i++)
	{
		int n, c;
		scanf("%d %d", &n, &c);
		guests.push_back(Guest(n, c));
	}
	sort(capacity.begin(), capacity.end());
	sort(guests.begin(), guests.end());
	long sum = 0;
	for (size_t i = 0; (i < m) && capacity.size(); i++)
	{
		vector<int>::iterator fd = lower_bound(capacity.begin(), capacity.end(), guests[i].num);
		if (fd!=capacity.end())
		{
			capacity.erase(fd);
			sum += guests[i].cost;
		}
	}
	printf("%ld\n", sum);


}

C++ 解法, 执行用时: 10ms, 内存消耗: 8860KB, 提交时间: 2017-05-08

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct guest
{
	int num, cost;
};

int cmp(guest a, guest b)
{
	return a.cost > b.cost;
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> cap(n);
	for (int i = 0; i < n; i++)
	{
		cin >> cap[i];
	}
	vector<guest> g(m);
	for (int i = 0; i < m; i++)
	{
		cin >> g[i].num >> g[i].cost;
	}
	sort(g.begin(),g.end(),cmp);
    	sort(cap.begin(),cap.end());

	long long ans = 0;
	for (int i = 0; i < m; i++)
	{
		//for (int j = 0; j < n; j++)
		for(vector<int>::iterator j = cap.begin(); j!=cap.end(); j++)
		{
			if(g[i].num <= *j)
			{
				ans += g[i].cost;
				cap.erase(j);
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

详情