输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行,每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。
输出一个整数,表示最大的总预计消费金额
3 5 2 4 2 1 3 3 5 3 7 5 9 1 10
20
#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; }
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); } }//贪心,每次取出钱最多的,然后在桌子里面二分,找到正好能装下这桌人的桌子 //找到了就把答案加上这桌人能出的钱,然后删掉这张桌子。
#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; }
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; }
#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; }
思路:优先选消费额度大的客人安排就餐
#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); }
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))
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;
cin >> n >> m;
int x,y,z;
vector<int> vec_table;
vector<pair<int, int>> nums_bills;
size_t bill_res = 0;
for(int i = 0; i < n; i++){
cin >> x;
vec_table.push_back(x);
}
sort(vec_table.begin(), vec_table.end());
for(int i = 0; i < m; i++){
cin >> y >> z;
if(y <= vec_table.back()){
nums_bills.push_back(make_pair(y, z));
}
}
sort(nums_bills.begin(),nums_bills.end(),
[](pair<int, int> p1, pair<int, int> p2){return p1.second > p2.second;});
for(auto p : nums_bills){
if(vec_table.empty()) break;
auto it = lower_bound(vec_table.begin(), vec_table.end(), p.first);
if (it != vec_table.end())
{
vec_table.erase(it);
bill_res += p.second;
}
}
cout<<bill_res<<endl;
return 0;
}