- 魔术卷 1037 Magic Coupon (25 point(s))
- 排成最小的数字 1038 Recover the Smallest Number (30 point(s))
- 用 Swap(0, i) 操作进行排序 1067 Sort with Swap(0, i) (25 point(s))
火星上的魔术商店正在提供一些魔术优惠券。
每个优惠券上都印有一个整数
此外，该商店还免费提供一些赠品。
如果你将印有正整数
但是，神奇的是，他们有一些
例如，给定一组优惠券，上面印的数字依次为 {1 2 4 -1} 以及一组产品，价值分别为 {7 6 -2 -3}（产品价值为负的是赠品）。
你可以使用第三张优惠券购买第一个产品，得到
也就是说，你通过合理使用优惠券，最多可以从商店那里拿走
现在，给定你若干的优惠券和若干的商品，每个优惠券和商品最多只能选择一次，请问你最多可以从商店里拿回多少钱。
第一行包含一个整数
第二行包含
第三行包含一个整数
第四行包含
输出一个整数，表示最多可以拿回的钱数。
-
$1 \le N_c,N_p \le 10^5$ , - 输入的两个整数序列中的元素的绝对值均不超过
$100$ 。
4
1 2 4 -1
4
7 6 -2 -343The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product... but hey, magically, they have some coupons with negative N's!
For example, given a set of coupons { 1 2 4 −1 }, and a set of product values { 7 6 −2 −3 } (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.
Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.
Each input file contains one test case. For each case, the first line contains the number of coupons
For each test case, simply print in a line the maximum amount of money you can get back.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]);
sort(a, a + n); // 贪心问题，排序
sort(b, b + m);
int res = 0;
for (int i = 0, j = 0; i < n && j < m && a[i] < 0 && b[j] < 0; i ++, j ++ )
res += a[i] * b[j]; // 负数相乘
for (int i = n - 1, j = m - 1; i >= 0 && j >= 0 && a[i] > 0 && b[j] > 0; i --, j -- )
res += a[i] * b[j]; // 正数相乘
printf("%d\n", res);
return 0;
}给定一个数组，数组中包含若干个整数，数组中整数可能包含前导
你需要将数组中的所有数字拼接起来排成一个数，并使得该数字尽可能小。
例如，给定一个数组 32-321-3214-0229-87 或 0229-32-87-321-3214，而能排列出的最小的数字为 0229-321-3214-32-87。
共一行，首先包含一个整数
输出能排列出的最小数字。
注意，结果的前导
5 32 321 3214 0229 8722932132143287Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.
Each input file contains one test case. Each case gives a positive integer
For each test case, print the smallest number in one line. Notice that the first digit must not be zero.
// 定义了 a + b < b + a 比较字典序这种比较方法
// 对于字符串数字 a[i] > a[i+1] 充分必要条件为 a[i]a[i+1] > a[i+1]a[i]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
string str[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> str[i];
sort(str, str + n, [](string a, string b) {
return a + b < b + a; // b 比 a 大
});
string res;
for (int i = 0; i < n; i ++ ) res += str[i];
int k = 0;
while (k + 1 < res.size() && res[k] == '0') k ++ ; // 删掉前导零，此外，k+1为了保存0
cout << res.substr(k) << endl;
return 0;
}给定一个
如果只能使用 Swap(0, *) 操作（将数字
例如，给定序列 {4, 0, 2, 1, 3}，我们可以通过下列交换操作，得到升序序列：
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}现在，请你求出将给定序列按如上交换操作变为升序序列，至少需要多少步操作。
第一行包含整数
第二行包含一个
输出所需最少操作步数。
10
3 5 7 2 6 4 9 0 8 19Given any permutation of the numbers {0, 1, 2,..., N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.
Each input file contains one test case, which gives a positive {0, 1, ..., N−1}. All the numbers in a line are separated by a space.
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
如上，本题可以构建图。该图出度入度都一定为 1 。
如上，性质为：
- 0 和 环内点交换，分为 2 个环
- 0 和 环外点交换，合并为 1 个环
则：
- 把 0 与其下一节点交换，由此全都把环变为自环 （
i=p[i]，数字i处于p[i]） - 然后 0 再去找其他不是自环的环，再把其点都变为自环
// 转换为图论问题，如图， i 在 p[i] 位置上，则 i 指向 p[i]
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int p[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int id;
scanf("%d", &id);
p[id] = i;
}
int res = 0;
for (int i = 1; i < n;)
{
while (p[0]) swap(p[0], p[p[0]]), res ++ ; // p[0] 不指向 0 ，把环上点变为自环
while (i < n && p[i] == i) i ++ ; // 找下一个不是自环的环
if (i < n) swap(p[0], p[i]), res ++ ; // 让 0 进入该环
}
printf("%d\n", res);
return 0;
}