滴滴笔试餐桌问题如何求解？

不是看不起n^2暴力，但是，下手写之前，估算一下你们写的东西要跑多久，ok？ 这里n^2暴力，是25亿，当电脑1秒算2亿吧（i7-4700HQ，全速的结果），那你也得跑12秒，这题时限1秒，怎么想都不应该。

这题就是卡复杂度，偷懒不用二分都要被超时~~ 二分js也能过。

暴力贪心解法，应该能用二分法优化，考试没时间了 #include<iostream> #include<vector> #include<algorithm> using namespace std; struct customer { int people; int money; }; bool compare(customer a, customer b) { return a.money>b.money; } int main() { int n=0, m=0; cin >> n >> m; vector<int>table(n, 0); vector<int>take(n, 0); for (int i = 0; i<n; ++i) cin >> table[i]; vector<customer>c; while (m-->0) { customer tmp; cin >> tmp.people; cin >> tmp.money; c.push_back(tmp); } sort(c.begin(), c.end(), compare); sort(table.begin(), table.end()); int fee = 0; for (int i = 0; i < c.size(); ++i) { for (int j = 0; j < n; ++j) { if (c[i].people <= table[j]&&take[j]==0) { take[j] = 1; fee += c[i].money; break; } } } cout << fee<<endl; }

目前只想到，基于数据结构维护的贪心。 思路：从高贵到低贱服务，相同的价格的？人数少的优先。 然后对每个人，找一张桌子，这张桌子是剩余桌子中刚刚好满足要求的。 ——使用平衡树比较好，比如C++的multiset，这样每次是logn的 嗯，就这样。 #include <stdio.h> #include <set> #include <algorithm> using namespace std; int desk[50005]; struct Pep { int num; int price; bool operator<(const Pep&b)const { if (price != b.price)return price > b.price; return num < b.num; } void get() { scanf("%d%d", &num, &price); } }pep[50005]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &desk[i]); } for (int i = 0; i < m; ++i) { pep[i].get(); } multiset<int> dsize; for (int i = 0; i < n; ++i) { dsize.insert(desk[i]); } sort(pep, pep + m); long long ans = 0; for (int i = 0; i < m; ++i) { multiset<int>::iterator it = dsize.lower_bound(pep[i].num); if (it == dsize.end())continue; while (it != dsize.begin() && *it > pep[i].num) --it; while (it != dsize.end() && *it < pep[i].num) ++it; if (it == dsize.end()) --it; if (it != dsize.end()) { ans += pep[i].price; dsize.erase(it); } } printf("%lld\n", ans); return 0; }

#include<iostream> #include <algorithm> #include<vector> using namespace std; int f(vector<int>&a, vector<vector<int>>&bc) { int lena = a.size(), lenbc = bc.size(); vector<int>temp(lenbc + 1, 0); vector<vector<int>>sum(lena + 1, temp); for (int i = 0; i <= lenbc; i++) sum[lena][i] = 0; for (int i = 0; i <= lena; i++) sum[i][lenbc] = 0; for (int i = lena - 1; i >= 0; i--) for (int j = lenbc - 1; j >= 0; j--) { int t1 = 0, t2 = 0; if (bc[j][0] <= a[i])t1 = sum[i + 1][j + 1] + bc[j][1]; t2 = sum[i][j + 1]; sum[i][j] = t1>t2 ? t1 : t2; } return sum[0][0]; } int cmp(vector<int>a, vector<int>b) { return a[0]<b[0]; } int main() { int n, m; cin >> n >> m; vector<int>a(n, 0); vector<int>temp(2, 0); vector<vector<int>>bc(m, temp); for (int i = 0; i<n; i++) cin>>a[i]; sort(a.begin(), a.end()); for (int i = 0; i<m; i++) { cin >> bc[i][0] >> bc[i][1]; } sort(bc.begin(), bc.end(), cmp); cout << f(a, bc) << endl; return 0; } 一样只过了20%,不知道哪儿有问题

package didiexam; import java.util.Arrays; import java.util.Scanner; public class Main2 { public static void main(String[] args){ Scanner cin = new Scanner(System.in); while(cin.hasNext()){ int n = cin.nextInt(); int m = cin.nextInt(); int a[] = new int[n]; for(int i = 0; i< n; i++){ a[i] = cin.nextInt(); } int people[] = new int[m]; int money[] = new int[m]; for(int i = 0; i<m; i++){ people[i] = cin.nextInt(); money[i] = cin.nextInt(); } Arrays.sort(a); int maxvalue = 0; int tempmax = 0; int indexmax = -1; int table = 0; for(int i = 0; i<m; i++){ tempmax = 0; indexmax = -1; boolean find = false; for(int j = m-1; j>=0; j--){ if(money[j] > tempmax){ tempmax = money[j]; indexmax = j; } } for(int j = 0; j<n ;j++){ if(people[indexmax] <= a[j]){ maxvalue +=tempmax; money[indexmax] = 0; people[indexmax] = 0; a[j] = 0; find = true; table++; break; } } if(!find){ money[indexmax] = 0; people[indexmax] = 0; } if(table == n){ break; } } System.out.println(maxvalue); } } } 运行时间太长，没有通过测试。哎！只过了20%