蓝桥杯专题之思维篇_小蓝要在路边划分停车位。 　　他将路边可停车的区域划分为 l 个整数小块,编号 1

题目列表：

2014年：蚂蚁感冒

2016年：交换瓶子

2018年：乘积最大

2019年：后缀表达式

2022年第一次模拟赛：停车位

1.蚂蚁感冒

题目描述
长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
输入
第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。

接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。
输出
要求输出1个整数，表示最后感冒蚂蚁的数目。
样例输入
3
5 -2 8
5
-10 8 -20 12 25
样例输出
1
3

分析：

当两只蚂蚁碰面时，他们会同时掉头往相反的方向爬行。

其实我们不要将蚂蚁区别化，哦，这只蚂蚁怎么走，那只蚂蚁怎么走，完全不需要这样，你这样一只一只的看，假如给你100只蚂蚁，你难道还要把他们的运动轨迹一一记录下来吗！！

从左边来的蚂蚁和从右边来的蚂蚁碰面后掉头，掉头以后，还是有一只蚂蚁在向左走，有一只蚂蚁在向右走，所以我们完全可以当成什么都没有发生，从左边来的蚂蚁仍然向右走，从右边来的蚂蚁仍然向左走，两只中只要有一只感冒了，两只都感冒

如果感冒的蚂蚁向右走，判断有多少只蚂蚁在它的右边并且向左走，这些蚂蚁是要被传染的，还有在他身后也在向右走的蚂蚁，他们也是要被传染的

如果感冒的蚂蚁向左走，判断有多少只蚂蚁在它的左边并且向右走，这些蚂蚁是要被传染的，还有在他身后也在向左走的蚂蚁，他们也是要被传染的

代码：

#include<iostream>
#include<cmath>
using namespace std;
int main(){
	int n;
	cin >> n;
	int cnt = 1;
	int first;
	cin >> first;
	int k;
	for(int i = 0;i < n-1;i++){
		cin >> k;
		if(first > 0){
			if((abs(k) > first && k < 0) || (k > 0 && k < first)){
				cnt++;
			}
		}else{
			if((abs(k) < abs(first) && k > 0) || (k < 0 && abs(k) > abs(first))){
				cnt++;
			}
		}
	}
	cout << cnt;
	return 0;
}

2.交换瓶子

题目描述

有N个瓶子，编号 1 ~ N，放在架子上。

比如有5个瓶子：
2 1 3 5 4

要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5

对于这么简单的情况，显然，至少需要交换2次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。

输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

例如，输入：
5
3 1 2 5 4

程序应该输出：
3

再例如，输入：
5
5 4 3 2 1

程序应该输出：
2

分析：

这道题我刚写的时候想到了逆序对，正一遍求逆序对再逆过来再求一遍逆序对，两遍地结果相加正好是每个数需要移动的次数，但是这个移动是怎么个移法，他是每次只能交换相邻两个元素；

例：

        3   1   2   5   4

正： 0   1   1   0   1

+

反： 2   0   0   1   0

=      2   1   1   1   1

但是这道题它可以随便交换，所以这种求法在这里就不适用了

但是，我们可以发现：

5    1    4    2    3

从第一个数开始移，5不在正确的位置，需要交换；交换后，3    1    4    2    5

指针先不着急往后移，要检查交换过来的数是否也在正确的位置上，如果不在，继续交换（这有点 像快排的思想，右边的数交换过来后不着急向后走，再检查换过来的这个数）

3不在正确的位置，需要交换；交换后，4    1    3    2    5

4不在正确的位置，需要交换，交换后，2    1    3    4    5

2不在正确的位置，需要交换，交换后，1    2    3    4    5

最终，所有的数都回到了自己的位置

代码：

#include<iostream>
using namespace std;
const int MAX_N = 10010;
int N;
int a[MAX_N];
int main(){
	cin >> N;
	for(int i = 1;i <= N;i++){
		cin >> a[i];
	}
	int cnt = 0;
	for(int i = 1;i <= N;){
		if(i != a[i]){
			int temp = a[i];
			a[i] = a[temp];
			a[temp] = temp;
			cnt++;
		}else{
			i++;
		}
	}
	cout << cnt;
	return 0;
}

3.乘积最大

【问题描述】

给定 N 个整数 A1,A2, …, AN。

请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009的余数，即：0−((0−x)%1000000009)

【输入格式】
第一行包含两个整数 N 和 K。
以下 N 行每行一个整数 Ai。

【输出格式】
输出一个整数，表示答案。

【输入样例1】

5 3

-100000

-10000

2

100000

10000

【输出样例1】

999100009

【输入样例2】

5 3

-100000

-100000

-2

-100000

-100000

【输出样例2】

-999999829

【评测用例规模与约定】
1 ≤ K ≤ N ≤ 1e5
−1e5 ≤ Ai ≤ 1e5

分析：

1.如果正数（包括0）的个数大于等于k，那么就从正数中从大到小选K个数相乘

2.如果正数（包括0）的个数小于k（设正数的个数为g）

        如果k-g=偶数，就从负数中从小到大选k-g个数，再与g个正数相乘

        如果k-g=奇数，就从负数中从大到小选k-g个数，再与g个正数相乘

代码（只过了40%的数据，自己也不知道问题出在哪，如果有大佬路过，可以帮我指出来吗，感谢^^）：

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5+10;
const long long MOD = 1e9+9;
int N,K;
int a[MAX_N],b[MAX_N];
long long ans = 1;
bool mycmp(int a,int b){
	return a > b;
}
int main(){
	cin >> N >> K;
	int m,j = 0,l = 0;
	for(int i = 0;i < N;i++){
		cin >> m;
		if(a[i] >= 0){
			a[j++] = m;
		}else{
			b[l++] = m;
		}
	}
	if(j >= K){
		sort(a,a+j,mycmp);
		for(int i = 0;i < K;i++){
			ans *= a[i];
		}
		cout << ans % MOD;
	}else{
		for(int i = 0;i < j;i++){
			ans *= a[i];
		}
		if((K-j) % 2 ==0){
			sort(b,b+l);
			for(int i = 0;i < K-j;i++){
				ans *= b[i];
			}
			cout << ans%MOD;
		}else{
			sort(b,b+l,mycmp);
			for(int i = 0;i < K-j;i++){
				ans *= b[i];
			}
			cout << -((0-ans)%MOD);
		}
	}
	return 0;
}

4.后缀表达式

 题目描述
给定N 个加号、M 个减号以及N + M + 1 个整数A1,A2,…,AN+M+1
小明想知道在所有由这N 个加号、M 个减号以及N + M +1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用1 2 3 + -，则“2 3 + 1 -” 这个后缀表达式结果是4，是最大的。

输入
第一行包含两个整数N 和M。
第二行包含N + M + 1 个整数A1,A2,…,AN+M+1
0<=N,M<=100000,-109<=Ai<=109

输出
输出一个整数，代表答案。

样例输入
1 1
1 2 3

样例输出
4

分析：

如果全是正号，将全部的数相加即可

如果既有正号又有负号，无论负号有多少个，最后都只剩下一个负号

例：假如有一个负号：-a1；两个负号：-（a1-a2)=-a1+a2；三个负号：-(a1-a2-a3) = -a1+a2+a3

所以 如果全为正数，那么那一个负号就减去最小的正数

        如果全为负数或既有正数也有负数，那么那一个负号就减去最小的负数

后缀表达式存在优先级，所以可以任意加括号！！！

意思就是：遇到负数就减，遇到正数就加（举个例子就好理解了^^）

例：3   2   -1    -2   -6      2个加号，3个减号

其后缀表达式为：-（-6 + (-2) + (-1) - 2 - 3）

最后还有个地方需要注意：

        在面对大流量的输入时，尽量使用scanf，会比cin快很多！！！

代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int N,M;
const int MAX_N = 2*(1e5+10);
int a[MAX_N];
long long ans;
int main(){
	cin >> N >> M;
	int k = N+M+1;
	for(int i = 0;i < k;i++){
		scanf("%d",&a[i]);
	}
	if(!M){
		for(int i = 0;i < k;i++){
			ans += a[i];
		}
	}else{
		sort(a,a+k);
		ans -= a[0];
		for(int i = 1;i < k;i++){
			ans += abs(a[i]);
		}
	}
	cout << ans;
	return 0;
} 

5.停车位

【问题描述】

​ 小蓝要在路边划分停车位。

​ 他将路边可停车的区域划分为 L个整数小块，编号1至L。一个车位需要连续的 K 个小块，停车位不能重叠。有的小块属于井盖、消防通道等区域，不能停车。

​ 请问小蓝最多划分出多少个停车位？

【输入格式】

​ 输入的第一行包含三个整数 L、K、N，分别表示小块数量、一个车位需要的小块数量和不能停车的小块数量，相邻整数之间用一个空格分隔。

​ 第二行包含 N 个整数a[1], a[2], …， a[n]，按从小到大的顺序排列，相邻的整数间用空格分隔，表示这些位置不能停车。

【输出格式】

​ 输出一行包含一个整数，表示答案。

【样例输入】

100 10 2
25 91

【样例输出】

8

分析：

这道题的意思就是在那些可以停车的地方可以划分出多少个停车位

例：

一共有100个小块，其中第25个小块和第91个小块不能停车

也就是在第1~24个小块，第26~90个小块，第92~100个小块这三片区域可以切分多少个停车位

代码：

#include<iostream>
using namespace std;
int main(){
	int L,K,N;
	cin >> L >> K >> N;
	int no;
	int last = 1;
	int ans = 0;
	for(int i = 0;i < N;i++){
		cin >> no;
		ans += (no-last)/10;
		last = no+1;
	}
	cout << ans;
	return 0;
}

生活的每一天都很精彩，所以千万不要放弃啊！！