思路：
- 输出 \(\lfloor \frac{n}{x}
\rfloor\) 即可
时间复杂度：\(O(1)\)
1
2
3
4
5
6
7
8
9
10
11
| signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, x;
std::cin >> n >> x;
std::cout << n / x << "\n";
return 0;
}
|
思路：
我们可以分几种情况
- 当只有一种牛时，一定不成立
- 当牛的品种数大于
4一定不成立
- 当牛的品种数小于
4种，最大种类数只为1时，一定不成立
- 当牛的种类数小于
3种，且最少有一个种类数为1时，一定不成立
- 否则成立
时间复杂度：\(O(n)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s;
std::cin >> s;
std::unordered_map<char, int> cnt;
for (auto c : s) {
cnt[c]++;
}
int mn = INT_MAX, mx = 0;
for (auto [x, y] : cnt) {
mn = std::min(mn, y);
mx = std::max(mx, y);
}
if ((s.size() <= 3 && mx == 1) || (cnt.size() == 1) || cnt.size() > 4) {
std::cout << "No\n";
return 0;
}
if (cnt.size() <= 2 && mn == 1) {
std::cout << "No\n";
return 0;
}
std::cout << "Yes\n";
return 0;
}
|
思路：
- 将订单按照利润降序排序，将货车按载重量升序排序，从前往后枚举每一个订单，对于当前订单，从前往后找到第一辆未使用且可以容纳它的货车运输
关于贪心解的证明，可以看看AcWing的这一篇题解
时间复杂度：\(O(n \times k)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::array<int, 3>> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i][0] >> a[i][1];
a[i][2] = i;
}
int k;
std::cin >> k;
std::vector<std::pair<int, int>> b(k);
for (int i = 0; i < k; i++) {
int x;
std::cin >> x;
b[i] = {x, i};
}
std::sort(a.begin(), a.end(), [&](auto i, auto j) {
return i[1] > j[1];
});
std::sort(b.begin(), b.end());
std::vector<int> vis(n);
std::vector<std::pair<int, int>> ans;
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
if (!vis[j] && b[j].first >= a[i][0]) {
vis[j] = true;
ans.emplace_back(a[i][2], b[j].second);
sum += a[i][1];
break;
}
}
}
std::cout << ans.size() << " " << sum << "\n";
for (auto [x, y] : ans) {
std::cout << x + 1 << " " << y + 1 << "\n";
}
return 0;
}
|
