題目傳送門

解題思路

對于每種顏色的豆子，我們先找到美味度最小的那個，最后找出這些不同種類的豆子中美味度最大的即可。

那我們怎么找到第 $i$ 種豆子中美味度最小的那個呢？這里給出兩種思路：

1. 使用桶的思想標記。
2. 對于每一種的豆子按照美味度從大到小排序。

注意： 如果你使用的是思路一，那么你不能使用數組進行標記，因為數據范圍很大，因此我們可以使用 map 進行標記。

第一種思路的代碼：

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {int a, c;
}b[200010];
map<int, int> m;
signed main() {
ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> b[i].a >> b[i].c;if (m[b[i].c] == 0)m[b[i].c] = b[i].a;else m[b[i].c] = min(m[b[i].c], b[i].a);}int ans = -1e9;for (int i = 1; i <= n ;i ++){ans = max(m[b[i].c], ans);}cout << ans;return 0;
} 

第二種思路的代碼：

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {int a, c;
}b[200010];
map<int, int> m;
bool cmp(node a, node b){if (a.c != b.c)return a.c < b.c;return a.a < b.a;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++)cin >> b[i].a >> b[i].c;sort(b + 1, b + 1 + n, cmp);int ans = -1e9;for (int i = 1; i <= n; i++)if (b[i].c != b[i - 1].c)ans = max(ans, b[i].a);cout << ans;return 0;
}

總結

這道題目還是很水，主要考察的是桶或者結構體排序，如果需要程序運行速度更快，建議大家使用第二種方法完成這道題目，因為本題使用第二種方法比第一種方法快兩倍，如果需要以最快的速度完成這道題，那么建議使用第一種方法，因為代碼要短 $50$ 個字符。