餐馆

include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct custom {
    int num;
    int cost;
};
class queue_cmp {
public:
	bool operator()(custom a, custom b) {
		return a.cost < b.cost;
	}
};
bool sort_cmp(custom a, custom b) {
    return a.num < b.num;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> tables(n);
    vector<custom> customs(m);
    for(int i = 0; i < n; i++)
        cin >> tables[i];
    for(int i = 0; i < m; i++)
        cin >> customs[i].num >> customs[i].cost;
    sort(tables.begin(), tables.end());
    sort(customs.begin(), customs.end(),sort_cmp);
    priority_queue<custom, vector<custom>, queue_cmp> que;
    long long sum = 0;
    int j = 0;
    for(int i = 0; i < n; i++) {
        for(; j < m && customs[j].num <= tables[i]; j++)
        	que.push(customs[j]);
        if(que.empty()) continue;
        sum += que.top().cost;
        que.pop();
    }
    cout << sum << endl;
    return 0;
}

#include<stdio.h>
#include<queue>
#include<set>
using namespace std;
struct node{
	int cnt,money;
	node(int cnt,int money):cnt(cnt),money(money){}
	bool operator<(const node &x) const{
		return money==x.money?cnt<x.cnt:money<x.money;
	}
};
int main(){
	int N,i,M,x,y;
	while(scanf("%d%d",&N,&M)!=EOF){
		multiset<int> s;
		for(i=0;i<N;scanf("%d",&x),s.insert(x),i++);
		priority_queue<node> Q;
		for(i=0;i<M;scanf("%d%d",&x,&y),Q.push(node(x,y)),i++);
		long res=0;
		while(!Q.empty()){
			node t=Q.top(); Q.pop();
			multiset<int>::iterator it=s.lower_bound(t.cnt);
			if(it!=s.end()) res+=t.money,s.erase(it);
		}
		printf("%ld\n",res);
	}
}//贪心，每次取出钱最多的，然后在桌子里面二分，找到正好能装下这桌人的桌子
 //找到了就把答案加上这桌人能出的钱，然后删掉这张桌子。

n,m=[int(x) for x in input().split()] #在m批客人中选择n批上n个桌子
table=[int(x) for x in input().split()] #每个桌子可容纳的最大人数
cus=[[int(x) for x in input().split()] for i in range(m)] #分别表示第i批客人的人数和预计消费金额

table.sort()#将桌子按可容纳人数从小到大排列
cus=sorted(cus,key=lambda x:x[0])#按每批顾客的人数进行从小到大排序
money=0#总金额

for i in range(n):
    temp=[]#盛放第i个桌子可接受的顾客批j
    for j in range(len(cus)): #注意range中要用cus的length时时更新
        if cus[j][0]>table[i]:
            break
        temp.append(cus[j])
    temp=sorted(temp,key=lambda x: x[1])#按消费金额排序
    if temp:
        money+=temp[-1][1]
        cus.remove(temp[-1])#此批客人已就坐

print(money)

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
#include<fstream>
#include<stdlib.h>
#include<ctime>
#include<vector>
using namespace std;
#define FOR(i,LE,RI) for(i=LE;i<RI;++i)
#define MEM(x,i) memset(x,i,sizeof(x))
#define COUT(DATA,ED) printf("%d%c",DATA,ED)
#define CIN(val)  scanf("%d",&val)
#define LL long long
const int LE=2000000;
const int INF=2000000;
class Customer{
	public:
		int num;
		int fare;
		friend bool operator<(Customer a,Customer b){
			return a.fare>b.fare;
		}
};
bool cmp(Customer a,Customer b){
	return a.num>b.num;
}
priority_queue<Customer> feng;
Customer cus[60000];
int table_size[60000];
int n,m;
void init(){
	int i,j;
	CIN(n);
	CIN(m);
	FOR(i,0,n){
		CIN(table_size[i]);
	}
	table_size[n]=-1;
	sort(table_size,table_size+n+1);
	FOR(i,0,m){
		CIN(cus[i].num);
		CIN(cus[i].fare);
	}
	sort(cus,cus+m,cmp);
}
void set(){
	int i,j;
	int ptr=n;
	while(!feng.empty()) feng.pop();
	FOR(i,0,m){
		feng.push(cus[i]);
		if(cus[i].num>table_size[ptr]){
			feng.pop();
		}else{
			--ptr;
		}
	}
	LL sum=0,cur;
	Customer alt;
	while(!feng.empty()){
		alt=feng.top();
		feng.pop();
		cur=(LL)alt.fare;
		sum+=cur;
	}
	printf("%lld\n",sum);
}
int main(){

	init();
	set();
    return 0;
}

思路：优先选消费额度大的客人安排就餐

• 对客人按消费水平排序（大->小），对桌子按容量从小到大排序
• 对每批客人依次选择合适的桌子
  如果没有桌子可用，结束；
  如果人数过多无法安排，跳过；
  否则找到最合适的桌位，可就餐的桌位中容量最小的，计算res，并将该桌子从桌子资源中删除；
  直到没有桌子可用或所有客人全部安排

 #include <iostream>
 #include <string>
 #include <vector>
 #include <map>
 #include <algorithm>
 using namespace std;

 int main( )
 {
     int n,m,b,c;
     cin>>n>>m;
     vector<int> desk(n, 0);
     multimap<int, int, greater<int> > ump;
     for(int i=0;i < n; ++i){
         cin>>desk[i];
     }
     sort(desk.begin( ), desk.end());

     for(int i=0; i< m; ++i){
         cin>>b>>c;
         ump.insert(make_pair(c, b));
     }

     long long res = 0;
     for(auto& e : ump){  
         if(desk.empty()) break;
         int i=0; 
         while(i< desk.size() && desk[i] < e.second){
             ++i;
         }
         if(i == desk.size()) continue;//桌子容量装不下当前该批客人
         res += e.first;
        // cout<<"res: "<<res<<"   erase:"<<desk[i]<<endl;
         desk.erase(desk.begin()+i);
     }
     cout<<res<<endl;
     return 0;
 }

import bisect
table_num,custumer = map(int,input().split())
table_capacity = list(sorted((map(int,input().split()))))
c_m = [list(map(int,input().split())) for i in range(custumer)]
c_m = sorted(c_m,key=lambda x:[x[1],x[1]/x[0]],reverse = True)
money = 0
for cus,price in c_m:
    if not table_capacity:
        break
    index = bisect.bisect_left(table_capacity,cus)
    if index == len(table_capacity):
        continue
    else:
        money += price
        table_capacity.pop(index)
print(money)

table_num,custumer = map(int,input().split())
table_capacity = list(sorted((map(int,input().split())),reverse = True))
c_m = []
for i in range(custumer):
    c_m.append(list(map(int,input().split())))
c_m = sorted(c_m,key = lambda x:[x[1],x[0]],reverse = True)
money = 0
while table_capacity and c_m:
    chosen = c_m[0]
    c_m = c_m[1:]
    if table_capacity[0] < chosen[0]:
        continue
    differ = float('inf')
    for each in table_capacity:
        if 0 <= each - chosen[0] < differ:
            differ = each - chosen[0]
            ind = table_capacity.index(each)
    table_capacity.pop(ind)
    money += chosen[1]
print(money)

private static void getFeatTable(int[] max, int customeri, boolean[] already, int m) { 
//二分法进行查找 
int low = 0, high = max.length-1; 
while (low <= high){
 int mid = (low + high)/2;
 if (customeri > max[mid] ){
    low = mid + 1; 
}else if (customeri == max[mid]){ 
   if (already[mid]){ 
       low = mid + 1;
       break; 
   }else { 
       an --; 
       already[mid] = true; 
       money = money + m; 
       return; 
   } 
}else { high = mid - 1; } 
} 
while (low < max.length){ 
if (already[low]) 
 low++; 
else{ 
 an--; 
already[low] = true; 
money = money + m; 
return; } } } 

// 其实想法很简单，就是贪心算法，但是这个题目对时间卡的很紧
// 得用二分查找才行，搞了很久。
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n,m;
        while(sc.hasNext()){
            n = sc.nextInt();
            m = sc.nextInt();
            int[] p = new int[n];
            int[][] num = new int[m][2];
            for(int i=0;i<n;i++){
                p[i] = sc.nextInt();
            }
            Arrays.sort(p);
            int k=0;
            for(int i=0;i<m;i++){
                num[k][0] = sc.nextInt();
                num[k][1] = sc.nextInt();
                if(p[n-1]>=num[k][0]){
                    k++;
                }
            }
            Arrays.sort(num,0,k,new Comparator<int[]>(){
                public int compare(int[] a, int[] b){
                    return b[1]-a[1];
                }
            });
            boolean[] isSelect = new boolean[n];
            long sum = 0;
            int index = 0;
            for(int i=0;i<k;i++){
                index = findTable(p, num[i][0]);
                while(index<n && isSelect[index])index++;
                if(index<n){
                    sum += num[i][1];
                	isSelect[index] = true;
                }
            }
            System.out.println(sum);
        }
    }
    public static int findTable(int[] table, int people){
        int i=0,j=table.length-1;
        int index = (i+j)/2;
        while(i<=j){
            if(table[index]>=people){
                j = index - 1;
            }else{
                i = index + 1;
            }
            index = (i+j)/2;
        }
        if(table[index]<people)index++;
        return index;
    }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn=5e4;
int a[maxn+5];
int b[maxn+5];
int c[maxn+5];

struct node{
    int b,c;
    void read(){
        scanf("%d%d",&b,&c);
    }

    bool operator<(const node& rhs)const{
        if(c!=rhs.c)return c>rhs.c;
        return b<rhs.b;
    }
};

node p[maxn+5];

int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)p[i].read();
    sort(a+1,a+1+n);
    sort(p+1,p+1+m,less<node>());
    LL sum=0;
    bitset<maxn+5>vis;
    for(int i=1;i<=m;i++){
        int j=lower_bound(a+1,a+1+n,p[i].b)-a;
        while(j<=n&&vis[j])j++;
        if(j<=n){
            sum+=p[i].c;
            vis[j]=true;
        }
    }
    printf("%lld\n",sum);
}

#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;
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc  = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();  // n table
            int m = sc.nextInt();  // m customers
            int[] table = new int[n];
            for(int i=0;i<n;i++)
                table[i]=sc.nextInt();  // volume of a table
            
            int[][] cus = new int[m][2];
            for(int j=0;j<m;j++){
                cus[j][0]=sc.nextInt(); // number of customers
                cus[j][1]=sc.nextInt(); // money
            }
            
            Arrays.sort(table);
            Arrays.sort(cus, new Comparator<int[]>(){

	        public int compare(int[] a, int[] b){



	           return b[1]-a[1];

}
            });
            
            long res = 0L;
            int index = 0;
            boolean[] tableb = new boolean[n];
            for(int i=0;i<m;i++){
                if(cus[i][0]>table[n-1])
                    continue;
                index = bs(table,cus[i][0]);
                while(index<n && tableb[index]==true)
                    index++;
                if(index<n){
                    res += cus[i][1];
                    tableb[index]=true;
                }
            }
            
            System.out.println(res);
        }
        sc.close();
    }
    
    private static int bs(int[] num, int tar){
        int low=0;
        int high=num.length-1;
        int mid=0;
        while(low<=high){
            mid=(high+low)>>1;
            if(num[mid]>=tar)
                high=mid-1;
            else
                low=mid+1;
        }
        
        return low;
    }
}

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[] disk = new int[n]; //桌子数组
			for (int i = 0; i < n; i ++) {
				disk[i] = sc.nextInt();
			}
			Arrays.sort(disk); // 桌子容纳量从小到大排序
			PriorityQueue<Customer> queue = new PriorityQueue<>(); // 将客人按消费额降序加入优先级队列
			for (int i = 0; i < m; i ++) {
				int b = sc.nextInt();
				int c = sc.nextInt();
				if(b <= disk[n - 1]) queue.add(new Customer(b, c)); // 如果人数小于桌子最大容纳量,加入队列
			}
			boolean[] visited = new boolean[n]; // 记录桌子是否被占用
			long sum = 0; // 记录总盈利
			int count = 0; // 记录已使用的桌子数
			while ( ! queue.isEmpty()) {
				Customer customer = queue.poll();
				for (int i = 0; i < n; i ++) { // 为客人分配桌子
					if(customer.peopleCount <= disk[i] && ! visited[i]) {
						sum += customer.moneyCount;
						visited[i] = true;
						count ++;
						break;
					}
				}
				if(count == n) break;
			}
			System.out.println(sum);
		}
	}

	static class Customer implements Comparable<Customer> {
		private int peopleCount;
		private int moneyCount;

		public Customer(int peopleCount, int moneyCount) {
			this.peopleCount = peopleCount;
			this.moneyCount = moneyCount;
		}

		@Override
		public int compareTo(Customer o) {
			if(o.moneyCount > this.moneyCount) return 1;
			else if(o.moneyCount < this.moneyCount) return - 1;
			return 0;
		}
	}
}

/*
思路：优先选消费额度大的客人安排就餐
对客人按照消费额度排序（大->小）
对桌子按照容量排序（大->小）
选取当前消费额度最大客人：
1.如果没有桌子可用，结束；
2.如果人数过多无法安排，跳过；
3.如果可安排，则找到最合适的桌位，可就餐的桌位中容量最小的；
  3.1向这批客人收费；
  3.2将桌子从可用资源中删除；
直到没有桌子可用或所有客人全部安排
*/
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
    int n, m, b, c;
    int num;
    vector<int> desk;//可用桌子资源的容量
    vector<pair<int, int>> customer;//预计消费，人数
    cin >> n >> m;
    while(n--)//输入桌子容量
    {
        cin >> num;
        desk.push_back(num);
    }
    //对桌子容量从大到小排序
    sort(desk.begin(), desk.end());
    reverse(desk.begin(), desk.end());
    vector<bool> flag(desk.size(), false);
    while(m--)
    {
        cin >> b >> c;
        customer.push_back(make_pair(c, b));
    }
    //对顾客按消费额度从大到小排序
    sort(customer.begin(), customer.end());
    reverse(customer.begin(), customer.end());
    
    long long ret = 0;//必须是long long，int会溢出
    for(int it = 0; it < customer.size(); ++it)
    {
        if(desk.size() == 0)//没有可用的桌子了
            break;
        int consumeMoney = customer[it].first;
        int countOfPeople = customer[it].second;
        if(desk[0] < countOfPeople)//最大的桌子也容不下这批客人
            continue;
        int i = 0;
        while(i < desk.size() && desk[i] >= countOfPeople)//找到可以容纳这批客人的最小桌子
            ++i;//i为第一个不可容纳的桌子，则i-1位这批客人的最佳桌位
        ret = ret + consumeMoney;//收入增加
        desk.erase(desk.begin() + i - 1);//桌子从可用资源中删除
    }
    cout << ret << endl;
}

import sys

def binarySearach(target, array):
    if array == []:
        return -1
    if target <= array[0]:
        return 0
    if target > array[-1]:
        return -1

    lo, hi = 0, len(array) - 1

    while lo + 1 != hi:
        mid = int((lo + hi) / 2)
        if target <= array[mid]:
            hi = mid
        else:
            lo = mid
    return hi


def findSolution(customers, capacity, numOfTables):
    maxValue = 0
    count = 0
    for i in range(len(customers)):
        idx = binarySearach(customers[i][0], capacity)
        if idx >= 0:
            count += 1
            maxValue += customers[i][1]
            # print('current = ', customers[i])
            del capacity[idx]
            if count == numOfTables:
                break
    return maxValue



args = list(map(int, sys.stdin.readline().strip().split()))
capacity = list(map(int, sys.stdin.readline().strip().split()))
maxCap = max(capacity)

numOfTables = args[0]
numOfCustomers = args[1]

customers = []
for i in range(numOfCustomers):
    arg = list(map(int, sys.stdin.readline().strip().split()))
    #if maxCap < args[0]:
    #    continue
    customers.append(arg)

# 排序 根据人数 降序
customers.sort(key=lambda k:k[0], reverse=True)
# 排序 根据金额 降序
customers.sort(key=lambda k:k[1], reverse=True)
# 升序
capacity.sort()

print(findSolution(customers, capacity, numOfTables))

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first<b.first;
}
int main(){
    int n,m;
    while(cin>>n>>m){
        vector<int> desk(n);
        vector<pair<int,int>> customer(m);
        for(int i=0; i<n; i++) cin>>desk[i];
        for(int i=0; i<m; i++){
            int a,b; cin>>a>>b;
            customer[i] = make_pair(a,b);
        }
        sort(desk.begin(),desk.end());
        sort(customer.begin(),customer.end(),cmp);
        //vector<vector<int>> sum(m+1, vector<int>(n+1));
        //优化点一：用二维数组报错，超过内存限制。。（通过40%的测试用例）
       //              那就用一维数组保存最大金额数，然后第二层循环要从尾部到头部
        vector<long long> sum(n+1);
        
        for(int i=1; i<=m; i++){
            for(int j=n; j>=1; j--){    //注意这里的循环是从j=n到j=1
                if(desk[j-1]>=customer[i-1].first){
                    sum[j] = max(sum[j-1]+customer[i-1].second, sum[j]);
                } else {
      //优化点二：没加break前，报错超时。。（通过80%的测试用例）
     //               那就加一个判断分支，不符合条件直接跳出来。因为我们的桌子容纳人数是升序，
    //                若第j张桌子容纳不了第i批客人，那么可以判断前面的桌子也肯定容纳不了。
                    break;
                } 
            }
        }
        cout<<sum[n]<<endl;
    }
    return 0;
}

def search(nums, target):
	if target <= nums[0]:
		return 0
	if target > nums[-1]:
		return -1
	l, r = 0, len(nums)-1
	while l+1 != r:
		m = (l+r) // 2
		if target <= nums[m]:
			r = m
		else:
			l = m
	return r

n, m = map(int, raw_input().split())
a = map(int, raw_input().split())
guest = []
for i in range(m):
	guest.append(map(int, raw_input().split()))
guest.sort(key = lambda t:t[1], reverse = True)
a.sort()
i = 0
val = 0
for j in range(m):
	index = search(a, guest[j][0])
	if index >= 0:
		i += 1
		val += guest[j][1]
		del a[index]
		if i == n:
			break
print val

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
	int n, m;//n张桌子，m批客人
	while (cin >> n >> m)
	{
		vector<int> num(n);
		for (auto &i : num)
			cin >> i;
		sort(num.begin(), num.end());
		multimap<int, int> table;
		for (int i = 0; i < m; i++)
		{
			int b,c;//人数和消费金额
			cin >> b >> c;
			table.insert({ c, b });
		}
		long long res = 0;
		auto map_it = table.rbegin();
		while (map_it != table.rend())
		{
			for (int i = 0; i < num.size();i++)
			{
				if (num[i] >= map_it->second)
				{
					res += map_it->first;
					num.erase(num.begin()+i);
					i--;
					break;
				}
			}
			map_it++;
		}
		cout <<res << endl;
	}
	return 0;
}