首页 > 其他分享 >第2课-枚举、排序、贪心

第2课-枚举、排序、贪心

时间：2024-10-14 15:13:34浏览次数：8  
标签：10 int cin long 枚举 vv using 排序 贪心

前言

如果认为自己代码没问题，换行问题，边界问题等都处理了还是不行，可以试试交 C++(GCC9) 该类型，因为部分题目是 UVA 上的老题，可能不支持新版本的 C++。

如果提交UNKNOWN ERROR，应该是没绑定UVA账号，洛谷右上角个人设置里去填写注册一下即可。

除法 Division

思路

这个题一定要注意输出格式！！！，最后一行 \(0\) 不能输出多余空格，建议是打个标记在最开头输出换行。

因为数字只有 \(0\sim 9\)，所有可以考虑全排列，但是对每次 \(n\) 都去跑全排列这个时间代价是 \(10!\) 级别的，难以承受，细想可以发现，其实对于每个 \(n\) 来说，有很多不必要的排列是不用去枚举的，所以我们可以预处理出 \(0\sim 9\) 的排列，然后根据前 \(5\) 位和后 \(5\) 位得到它们与 \(y\) 的关系，从而在询问的时候直接输出答案即可。

考虑更快优化，因为 \(\frac xy =n\)，且 \(2\leq n \leq 79\)，\(x\) 又是固定 \(5\) 位数，所以我们可以直接枚举 \(10234\sim98765\)，然后除去 \(n\) 得到 \(y\)，最后只要检查 \(x\) 与 \(y\) 是否满足排列的关系即可。

（全排列预处理）代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

struct Node {
	int x, y;
} ans[80][100000];

int cnt[100];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

	do {

		int x = 0, y = 0;
		for (int i = 0; i < 5; i ++) {
			x = x * 10 + a[i];
			y = y * 10 + a[i + 5];
		}

		if (x % y == 0 && x / y <= 79) {
			int d = x / y;
			cnt[d] ++;
			ans[d][cnt[d]].x = x;
			ans[d][cnt[d]].y = y;
		}

	} while (next_permutation(a, a + 10));

	int n, f = 0;
	while (scanf("%d", &n)) {
		if (n == 0) {
			break;
		}
        
		if (f == 1) printf("\n");
		f = 1;
        
		if (cnt[n] == 0) {
			printf("There are no solutions for %d.\n", n);
		} else {
			for (int i = 1; i <= cnt[n]; i ++) {
				printf("%05d / %05d = %d\n", ans[n][i].x, ans[n][i].y, n);
			}
		}
	}

	return 0;
}

（枚举优化）代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, F = 0;
	while (scanf("%d", &n)) {
		if (n == 0) {
			break;
		}
        
		if (F == 1) printf("\n");
		F = 1;

		int cnt = 0;
		for (int x = 10234; x <= 98765; x ++) {
			if (x % n == 0) {
				int y = x / n;

				int num[10] {};
				for (int i = 1; i <= 10000; i *= 10) {
					num[x / i % 10] ++;
					num[y / i % 10] ++;
				}

				int ok = 1;
				for (int i = 0; i <= 9; i ++) {
					if (num[i] == 0) {
						ok = 0;
					}
				}

				if (ok == 0) {
					continue;
				}

				cnt ++;
				printf("%05d / %05d = %d\n", x, y, n);
			}
		}

		if (cnt == 0) {
			printf("There are no solutions for %d.\n", n);
		}
	}

	return 0;
}

（优化预处理）代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

struct Node {
	int x, y;
} ans[80][100000];

int cnt[100];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	for (int x = 10234; x <= 98765; x ++) {
		for (int n = 2; n <= 79; n ++) {
			if (x % n == 0) {
				int y = x / n;

				int num[10] {};
				for (int i = 1; i <= 10000; i *= 10) {
					num[x / i % 10] ++;
					num[y / i % 10] ++;
				}

				int ok = 1;
				for (int i = 0; i <= 9; i ++) {
					if (num[i] == 0) {
						ok = 0;
					}
				}

				if (ok == 0) {
					continue;
				}
				cnt[n] ++;
				ans[n][cnt[n]].x = x;
				ans[n][cnt[n]].y = y;
			}
		}
	}

	int n, f = 0;
	while (scanf("%d", &n)) {
		if (n == 0) {
			break;
		}
        
		if (f == 1) printf("\n");
		f = 1;
        
		if (cnt[n] == 0) {
			printf("There are no solutions for %d.\n", n);
		} else {
			for (int i = 1; i <= cnt[n]; i ++) {
				printf("%05d / %05d = %d\n", ans[n][i].x, ans[n][i].y, n);
			}
		}
	}

	return 0;
}

最大乘积 Maximum Product

思路

枚举区间起点和终点，计算区间乘积，取最大值即可，注意答案可能会超过 int 范围，需用 long long。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 20;
i64 a[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, cnt = 0;
	while (cin >> n) {

		for (int i = 1; i <= n; i ++) {
			cin >> a[i];
		}

		i64 ans = 0;
		for (int l = 1; l <= n; l ++) {
			for (int r = l; r <= n; r++) {
				i64 res = 1;
				for (int k = l; k <= r; k++) {
					res *= a[k];
				}
				ans = max(ans, res);
			}
		}

		cout << "Case #" << ++cnt << ": The maximum product is " << ans << ".\n\n";
	}

	return 0;
}

分数拆分 Fractions Again?!

思路

由题目得 \(x,y\) 是正整数，有 \(x>0,y>0\)。

\[\because x\ge y \]

\[\therefore \frac 1x \le \frac 1y,且 \frac 1x = \frac 1k -\frac 1y =\frac{y-k}{ky} \]

\[\therefore \frac 1k - \frac 1y\le \frac 1y,y\le 2k,y>k \]

所以我们可以从 \(k+1\sim2k\) 枚举 \(y\)，然后算出 \(x\)，记录答案即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 20010;

int x[N], y[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int k;
	while (cin >> k) {

		int cnt = 0;
		for (int i = k + 1; i <= 2 * k; i ++) {
			if (i * k % (i - k) == 0) {
				cnt ++;
				y[cnt] = i, x[cnt] = i * k / (i - k);
			}
		}

		cout << cnt << '\n';
		for (int i = 1; i <= cnt; i++) {
			cout << "1/" << k << " = 1/" << x[i] << " + 1/" << y[i] << '\n';
		}

	}

	return 0;
}

P2141 [NOIP2014 普及组] 珠心算测验

思路

要求找到 \(x+y=z[x,y,z\in A]\)，因为数据很小，那么我们可以直接三次循环枚举 \(z,y,z\) 然后判断加数和被加数是否不相同，并且它们的和等于 \(z\)，注意，题目问的是集合 \(A\) 中有多少个数等于集合中另外两个不同的数的和，也就是说 \(2+4=6\) 和 \(1+5=6\) 这种只能算 \(1\) 次，所以我们可以另外用数组来判断 \(z\) 是否出现过，最后再循环一次，把出现过的数统计一下即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const int N = 110;
int a[N], ok[N * N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}

	for (int k = 1; k <= n; k ++) {
		for (int i = 1; i <= n; i ++) {
			for (int j = i + 1; j <= n; j ++) {
				if (a[i] != a[j] && a[i] + a[j] == a[k]) {
					ok[a[k]] = 1;
				}
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= N * N; i++) {
		if (ok[i] != 0) {
			ans ++;
		}
	}

	cout << ans << '\n';

	return 0;
}

P8772 [蓝桥杯 2022 省 A] 求和

思路

\[S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n} \]

根据这个式子，你当然可以暴力的双循环进行求和，但是提交你会发现 TLE，因为题目说了对于 \(100\%\) 的数据，\(1\le n\le 2\times 10^5\)，所以这个时候去双层循环显然计算机就承担不起 \(2\times 10^5 \times 2\times 10^5\) 的这样运算，因此我们需要优化。

仔细观察这个式子，其实我们可以尝试提取一下公因项，那么就可以得到：

\[S=a_1\cdot (a_2+a_3+\dots+a_n)+a_2\cdot (a_3+a_4+\dots+a_n)+\dots+a_{n-2}\cdot (a_{n-1}+a_n)+a_{n-1} \cdot a_n \]

诶！是不是有点规律了？

假如我们优先把 \(a_1+a_2+a_3+\dots+a_n=sum\) 计算出来，那我们每次循环的时候减去 \(a_i\)，那是不是就得到了 \(a_{i+1}+a_{i+2}+\dots+a_n\) 呢？

所以上述式子可以转变为：

\[S=\sum\limits_{i=1}^na_i\cdot(sum-\sum\limits_{j=1}^ia_j) \]

同理，另外一种方法，我们给它补上缺的 \(a_1+a_2+\dots+a_i\)，那最后就得到了

\[(a_1+a_2+\dots+a_n)\cdot sum-a_1\cdot a_1-a_2\cdot(a_1+a_2)-\dots-a_n\cdot(a_1+a_2+\dots+a_n) \]

即：

\[S=sum^2-\sum\limits_{i=1}^na_i\cdot(\sum\limits_{j=1}^ia_j) \]

不过最后这个方法感兴趣的同学可以自己写写，这里就只放第一种了。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const int N = 200100;
int a[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	long long sum = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum += a[i];
	}

	long long ans = 0;
	for (int i = 1; i <= n; i ++) {
		sum -= a[i];
		ans += sum * a[i];
	}

	cout << ans << '\n';

	return 0;
}

P1618 三连击（升级版）

思路

看到要求 \(1\sim9\) 的方案数，那自然想到一种暴力是全排列了，用上next_permutation这个函数，可以很快求得排列方案，需要注意这个函数最初的数列，必须要从最小到从大排列，所以一般会搭配sort使用，不过我们这里直接初始化了，就不用排序，然后就是根据比例关系 \(\frac ab=\frac xy\to a\times y=b\times x\) 判断是否合法，其他比例同理。

当然，和前面的那道题一样，我们也枚举三位数，然后根据比例计算出其他两个数，判断是否是 \(1\sim9\) 的排列即可。

（全排列）代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	long long a, b, c;
	cin >> a >> b >> c;

	int A[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

	int f = 0;
	do {

		int x = 0, y = 0, z = 0;
		for (int i = 0; i < 3; i ++) {
			x = x * 10 + A[i];
			y = y * 10 + A[i + 3];
			z = z * 10 + A[i + 6];
		}

		if (b * x == a * y && b * z == c * y && a * z == c * x) {
			f = 1;
			cout << x << ' ' << y << ' ' << z << '\n';
		}

	} while (next_permutation(A, A + 9));

	if(f == 0){
		cout << "No!!!\n";
	}

	return 0;
}

（枚举三位数）代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int a, b, c;
	cin >> a >> b >> c;

	if (a == 0) {
		cout << "No!!!\n";
		return 0;
	}

	bool f = false;
	for (int i = 123; i <= 329; i++) {
		int x = i, y = i * b / a, z = i * c / a;
		if (y < 100 || y > 1000 || z < 100 || z > 1000)continue;
		
		int vv[10] {};
		vv[x / 100] = vv[x / 10 % 10] = vv[x % 10] = 1;
		vv[y / 100] = vv[y / 10 % 10] = vv[y % 10] = 1;
		vv[z / 100] = vv[z / 10 % 10] = vv[z % 10] = 1;
		if (vv[1] && vv[2] && vv[3] && vv[4] && vv[5] && vv[6] && vv[7] && vv[8] && vv[9]) {
			cout << x << " " << y << " " << z << '\n';
			f = true;
		}
	}
	if (f == false) {
		cout << "No!!!" << '\n';
	}

	return 0;
}

B3968 [GESP202403 五级] 成绩排序

思路

此题考察自定义排序，强烈要求同学们好好写。

此外题中要求要按同学原来的顺序输出他们各自的排名，所以我们在按要求排完序后还得记录他们各自的排名，然后再按照他们原来的顺序再排序回去。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 10010;

struct Node {
	int c, m, e;
	int id, rank;
} a[N];

bool cmp(Node x, Node y) {
	if (x.c + x.m + x.e != y.c + y.m + y.e) {
		return x.c + x.m + x.e > y.c + y.m + y.e;
	}
	if (x.c + x.m != y.c + y.m) {
		return x.c + x.m > y.c + y.m;
	}
	if (max(x.c, x.m) != max(y.c, y.m)) {
		return max(x.c, x.m) > max(y.c, y.m);
	}
	return 1;
}

//根据id还原原来的顺序
bool cmp1(Node x, Node y) {
	return x.id < y.id;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i ++) {
		cin >> a[i].c >> a[i].m >> a[i].e;
		a[i].id = i;
	}

	sort(a + 1, a + 1 + n, cmp);

	a[1].rank = 1;
	for (int i = 2; i <= n; i ++) {
		a[i].rank = i;
		if (a[i].c + a[i].m + a[i].e == a[i - 1].c + a[i - 1].m + a[i - 1].e) {
			if (a[i].c + a[i].m == a[i - 1].c + a[i - 1].m) {
				if (max(a[i].c, a[i].m) == max(a[i - 1].c, a[i - 1].m))
					a[i].rank = a[i - 1].rank;
			}
		}
	}

	sort(a + 1, a + 1 + n, cmp1);

	for (int i = 1; i <= n; i ++) {
		cout << a[i].rank << '\n';
	}

	return 0;
}

P1177 【模板】排序

思路

考察排序的用法。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 100010;
int a[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}

	sort(a + 1, a + 1 + n);

	for (int i = 1; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}

P2676 [USACO07DEC] Bookshelf B

思路

要求我们用最少的奶牛叠到一定高度，就和用最少的钱凑成一定的数一样，贪心的选取最大的来凑，从大到小排序后，当某一个数凑起来大于了给定的数之后，输出这个数的位置即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 100010;
int a[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, w;
	cin >> n >> w;

	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}

	sort(a + 1, a + 1 + n, greater<>());

	int sum = 0;
	for (int i = 1; i <= n; i ++) {
		if (sum + a[i] < w) {
			sum += a[i];
		} else {
			cout << i << '\n';
			break;
		}
	}

	return 0;
}

P1478 陶陶摘苹果（升级版）

思路

和上面那道题类似，只不过这题问的是 \(s<0\) 之前最多能摘到多少苹果，所以当 \(s-A_i<0\) 的时候我们得输出 \(i-1\) 也就是最多只能摘 \(i-1\) 个苹果；

另外，题目要求 \(h_i\le a+b\) 的才可以摘，这种有个小技巧就是我们在输入的时候只把符合要求的记录下来，大于 \(a+b\) 的我们不记录即可，还有可能所有的苹果摘完了还没耗尽力气，这个直接输出我们能摘到的最多苹果数即可。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 100010;
int A[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, s, a, b;
	cin >> n >> s >> a >> b;

	int cnt = 0;
	for (int i = 1; i <= n; i ++) {
		int x, y;
		cin >> x >> y;
		if (x <= a + b) {
			cnt ++;
			A[cnt] = y;
		}
	}

	sort(A + 1, A + 1 + cnt);

	for (int i = 1; i <= cnt; i ++) {
		if (s >= A[i]) {
			s -= A[i];
		} else {
			cout << i - 1 << '\n';
			return 0;
		}
	}

	cout << cnt << '\n';

	return 0;
}

P1223 排队接水

思路

要使得整体的平均等待时间最短，那么只能让打水快的人先打，这样后面的人才能排队时间更短，否则让一个打得很慢的人排在前面，那么后面\(n-1\) 个人都得等他打完。

cout<<fixed<<setprecision(x)<< 是c++保留几位小数的函数，要保留几位，\(x\) 就填几，记不住也可以用C语言的 printf("%.2lf",ans)，不过要记住，c++的输入输出语法最好不要和C语言混用，要用printf，那么输入尽量也换成scanf。

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 100010;
struct Node {
	int time, id;
} a[N];

bool cmp(Node x, Node y) {
	return x.time < y.time;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i ++) {
		cin >> a[i].time;
		a[i].id = i;
	}

	sort(a + 1, a + 1 + n, cmp);

	double ans = 0, now = 0;
	for (int i = 1; i <= n; i ++) {
		cout << a[i].id << " ";

		ans += now;
		now += a[i].time;
	}

	ans /= n;
	cout << '\n';
	cout << fixed << setprecision(2) << ans << '\n';

	return 0;
}

标签：10,int,cin,long,枚举,vv,using,排序,贪心
From： https://www.cnblogs.com/Kescholar/p/18464250

相关文章

  • 再谈java枚举enum
    一、认识枚举枚举是一种特殊类枚举的定义：修饰符enum枚举名{枚举项1，枚举项2，枚举项3；其他成员；}注意：枚举的第一行只能写枚举项，多个枚举项用逗号（,），隔开每一个枚举项都是一个常量（不可改变值），且都指向一个该枚举的对象二、为什么要使用枚举例如，有这么一方......
  • 带中位数写法的快速排序再讨论 & leetcode 215. Kth Largest Element in an Array题解
    带中位数写法的快速排序再讨论&leetcode215.KthLargestElementinanArray题解 探讨带中位数的写法本身classSolution{public:intfindKthLargest(std::vector<int>&nums,intk){returnfakeQuickSort(nums,k,0,nums.size()-1);}privat......
  • Leetcode 贪心算法之Largest Number
    题目描述给定一组非负整数nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。实例示例1：输入：nums=[10,2]输出：“210”示例2：输入：nums=[3,30,34,5,9]输出：“9534330”思路分析利用贪......
  • C/C++贪心算法
    C++中的贪心算法一、基本概念贪心算法（又称贪婪算法，GreedyAlgorithm）是指，在对问题求解时，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题能产生整体最优解......
  • DAY31 ||贪心算法基础 | 455.分发饼干 |376.摆动序列 |53.最大子数组和
    贪心算法基础贪心算法是一种在求解问题时采取逐步构建解决方案的算法策略。它通过在每一步选择在当前看来最优的选择（即“贪心”选择），希望通过局部最优解的累积得到全局最优解。贪心算法的核心思想局部最优：每一步都选择在当前状态下最优的选择，不考虑后续步骤可能带来的影响。......
  • 【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研
     ......
  • 【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研
     ......
  • 贪心算法案例 - 零钱兑换问题
    贪心算法案例-零钱兑换问题贪心算法原则：每一次都选取当前最优解《向前看，别回头》案例：(322.零钱兑换-力扣（LeetCode）)题目描述：给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有......
  • Leetcode 贪心算法之 Container With Most Water
    题目描述给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。示例：输入：[1,8,6,2,5,4,8,3,7]输......
  • Leetcode 贪心算法之Jump Game II
    题目描述给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i+j]处:0<=j<=nums[i]i+j<n返回到达nums[n-1]的最小跳跃次数。生成的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99