总结 - 洛谷保存站

# T2
把两个极值放在$0$和$r$上，然后进行模拟，如果两个数最后都在同一个位置，就是成功。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int r , n;
	cin >> r >> n;
	int sum1 = 0;
    int sum2 = r;//两个极值
	bool flag = 0;
	for( int i = 1 ; i <= n ; i++)
	{
		int x;
		cin >> x;	
		sum1 += x;
        sum2 += x;
             
		if(sum1 > r)//越界
		{
			sum1 = r;
		}
		if(sum1 < 0)//越界
		{
			sum1 = 0;
		}
        if(sum2 > r)//越界
		{
			sum2 = r;
		}
		if(sum2 <= 0)//越界
		{
			sum2 = 0;
		}
	}
	if(sum1==sum2)//如果在同一个位置
	{
		cout << sum1 ;//随便输出一个
		return 0;
	}
	cout << -1;
	return 0;
}
```
---

# T3
这里正解是$bfs$（不可思议，对吧）。

首先，先压入原始数字$1,2,3,4,5,6,7,8,9$,然后开始$bfs$。

这里其实不难看出，每个原始数都有三种进化方式：

>##### 一、在原数的后面加原数个位-1（$$x*10+x\%10-1$$）
>##### 二、在原数的后面加原数个位（$$x*10+x\%10$$）
>##### 三、在原数的后面加原数个位+1（$$x*10+x\%10+1$$）
每次$while$循环相当于查找一个落落的去数，所以循环$k$次当前队首就是答案。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int k;
queue<int>q;
void bfs(int x)
{
	int cnt = 0;//统计当前个数
	while(q.size())
	{
		cnt++;//多查找了一个
		int f = q.front();
		q.pop();
		if(cnt==x)//如果就是答案
		{
			cout << f;//输出队首	
			return ;
		}
		for(int y = (f % 10) - 1 ; y <= (f %10)+1;y++)//这里跟方向数组一样的
		{
			if(y < 0||y>9)//不在范围内
			{
				continue;
			}
			q.push(f*10+y);//进化
		}
	}                                                     
	return;
}
signed main()
{
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);
	q.push(7);
	q.push(8);
	q.push(9);
        //其实我是原始人，不会for循环（doge）
	cin >> k;
	bfs(k);
	return 0;
}
```
---

# T4
**前缀和+二分**。

思路：可以把数组分成三部分（排序后）：

举例：
> $x=5$
> 
> $1,1,2,3,4,5,5,6,7,8$
> 
> 分成三部分：
> 
> $1,1,2,3,4$ 小于$x$的部分,答案是数量$*x-$和
>
> $5,5$等于$x$的部分，不用管
>
> $6,7,8$小于$x$的部分,答案是和$-$数量$*x$

答案是前后两个部分加起来。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int sum[1000000];
int a[1000000];
signed main()
{
	int n , q;
	cin >> n>> q;

for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i];
	
	}
		sort(a+1,a+1+n);//先排序，再前缀和
		for(int i = 1 ; i <= n ; i++)
	{
		
		sum[i]=sum[i-1]+a[i];
	}
	while(q--)
	{
		int x;
		cin >> x;
		int pos1 = lower_bound(a+1,a+1+n,x)-a-1;//求前面一段的终点下标
		int pos2 = upper_bound(a+1,a+1+n,x)-a;//求后面一段的起点下标
		int ans = 0;
		if (pos1!=0)//这里特判，如果pos1不等于0（lower_bound能查询到） ans+= (pos1)*x-sum[pos1];//加上前面部分答案，这里是上面公式加前缀和
		if (pos2!=n+1)//如果upper_bound查询得到 ans+= sum[n]-sum[pos2-1]-(n-pos2+1)*x;//加上后面答案
		cout << ans<<endl; 
	}
	return 0;
}
```

正在渲染内容...