蓝桥杯—算法训练

2021 年 4 月 18 日
笔记
算法

区间k大数查询

问题描述

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式

总共输出m行，每行一个数，表示询问的答案。

样例输入

5
1 2 3 4 5
2
1 5 2
2 3 2

样例输出

4
2

代码

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//输出 
void input(int* Num, int l, int r, int k)
{
	int i, j, * max, tmp, n = r - l+1, seq = l;
	max = (int*)calloc(n, sizeof(int));

	for (j = 0; j < n; j++)
	{
		max[j] = Num[seq++];
	}

	//冒泡排序
	for (i = 0; i < n; i++)
	{
		for (j = i + 1; j < n; j++)
		{
			if (max[j] > max[i])
			{
				tmp = max[i];
				max[i] = max[j];
				max[j] = tmp;
			}
		}
	}
	printf("%d\n", max[k - 1]);
	free(max);
}


int main(int argc, char* argv[])
{

	int n, m, * l, * r, * K, * Num, i;

	scanf("%d", &n);

	//输入数列 
	Num = (int*)calloc(n, sizeof(int));
	for (i = 0; i < n; i++)
	{
		scanf("%d", &Num[i]);
	}

	//输入条件 
	scanf("%d", &m);
	l = (int*)calloc(m, sizeof(int));
	r = (int*)calloc(m, sizeof(int));
	K = (int*)calloc(m, sizeof(int));
	for (i = 0; i < m; i++)
	{
		scanf("%d %d %d", &l[i], &r[i], &K[i]);
	}

	//开始操作
	for (i = 0; i < m; i++)
	{
		input(Num, l[i] - 1, r[i] - 1, K[i]);
	}

	free(Num);
	free(l);
	free(r);
	free(K);
	system("pause");
	return 0;
}

最大最小公倍数

问题描述

已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式

输入一个正整数N。

输出格式

输出一个整数，表示你找到的最小公倍数。

样例输入

样例输出

504

代码

方法1：

直接将所以的最小公倍数，存起来，再去找最小值，小点的数可以，大点的数就不行

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//求最大公约数
int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}
//求最小公倍数=两数之积/两数最大公约数
int lcm(int a, int b)
{
	if (a * b == 0)
		return 0;
	return (a * b) / gcd(a, b);
}

int LCM_lcm(int a, int b, int c)
{
	int tmp;
	tmp = lcm(a, b); 
	tmp = lcm(tmp, c);
	return tmp;
}


int main(int argc, char* argv[])
{

	int n, i, j, k, * LCM, lcmMax, g = 0;

	scanf("%d", &n);
	LCM = (int*)calloc(n * n * n, sizeof(int));

	//将所有的最小公倍数存于数组中 
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			for (k = 1; k <= n; k++)
			{
				LCM[g++] = LCM_lcm(i, j, k);
			}
		}
	}

	//找到最大值 
	lcmMax = LCM[0];
	for (i = 0; i < n * n * n; i++)
	{
		if (LCM[i] > lcmMax)
		{
			lcmMax = LCM[i];
		}
	}
	printf("%d\n", lcmMax);

	system("pause");
	return 0;
}

方法2：

参考：链接

首先，穷举法不适用

然后，求三个正整数的最小公倍数不会大于这三个数的乘积

因为，两个数互质时，它们的公倍数最大，即它们的乘积

那么三个数时，就是三个数两两互质时，即它们的最小公倍数最大，就是它们的乘积

故需要满足：

1.三个数两两互质

2.在满足a的条件下，使得三个整数取最大值

那么考虑N的取值：

a).N为奇数时

当N为奇数时，N – 1为偶数，N – 2为奇数，显然，数学知识告诉我们，相邻的两个正整数互质。同样的，相邻的两个奇数也是互质的，那么此时题目要求的答案为N * (N – 1) * (N – 2)

b).N为偶数时

因为当N >3时，N 和当N – 3是可能不是互质的，例如3和6。所以偶数时又分为两种可能性：

　　b1).当3不能整除N时

　　　　当N为偶数时，N – 2同样为偶数，那么就不能满足上面思路的第1点了。但是N和N – 1还是互质的，所以在贪心策略下，我们优先考虑使用更小的值去替换N – 2，而不是替换N 和 N – 1。

经计算发现 N – 3满足要求，所以此时答案为N * (N – 1) * (N – 3)【偶、奇、奇】

　　b2). 当3能整除N时

　　　　因为N能够被3整除，所以N – 3同样能被3整除，为了不违反第1点，我们再次优先用更小的值替代 N – 3

　　　　因为采用的是贪心策略，所以我们优先考虑使用N – 1去替换N，此时结果是：(N – 1) * (N – 2) * ( N – 3)。
　　显然相邻的两个正整数是互质的，我们只要考虑N – 1和N – 3是否互质就可以了。
因为N – 1和 N – 3实际上等同于第1种情况，即N为奇数时，故 (N – 1) * (N – 2) * ( N – 3)就是我们需要的点

代码

#include <stdio.h>

long long FindMax(long long N){
	long long res;       
	if(N <= 2)
		return N;
	
	if(N % 2 != 0){   //第一种情况，N为奇数时，最大最小公倍数为N * (N - 1) * (N - 2)
		res = N * (N - 1) * ( N - 2); 
	}
	else{
		if(N % 3 != 0)      //第二种情况 
			res = N *(N - 1) * (N - 3);
		else                   //第三种情况 
			res = (N - 1) * (N - 2)* (N - 3);
	}
	return res;
}

int main(){
	long long N;
	scanf("%lld",&N);
	printf("%lld",FindMax(N));
	return 0;
}

Tags: 算法