【蓝桥每日一题]-前缀和与差分（保姆级教程 篇3）#涂国旗 #重新排序

目录

题目：涂国旗

 思路：

题目：重新排序

 思路：

题目：涂国旗

 思路：

乍一看好像没啥思路，但是我们需要涂最少的格子，所以要都尝试一下才行，也就是从上面开始白至少一行，蓝若干行，红至少一行。

     

那么其实我们看到只需要控制好两个分割线即可。上面都是白，中间都是蓝，最下面都是红。然后比较每种情况所需要的最少代价即可。

     

最好是使用一下前缀和优化一下，这样答案就可以O(1)速度输出。

怎么前缀和呢？我们设置w[i]表示前面i行都涂成w颜色需要的代价即可！

#include <iostream>
#include <string>
using namespace std;
int n,m;string s;
inline int check(char c)      //化二维前缀和为一维前缀和
{
	int tol=0;
	for(int i=0;i<m;i++)
		if(s[i]!=c)tol++;	
	return tol;	
}
int main()
{
	cin>>n>>m;int w[n+1]={0},r[n+1]={0},b[n+1]={0};int ans=100000;  //ans必须很大
	for(int i=1;i<=n;i++)
	{	cin>>s;
		w[i]=w[i-1]+check('W');
		r[i]=r[i-1]+check('R');
		b[i]=b[i-1]+check('B');
	}
	for(int i=1;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		 ans=min(ans,w[i]+b[j]-b[i]+r[n]-r[j]);    //根据公式，遍历出最小的即可
		cout<<ans;
		return 0;
}

题目：重新排序

题意：对于一个长n的数组查询m次[l,r]区间，要想使所有查询和最大，我们就要排个序，现在就问排序后所以查询区间的总和相比原来可以增加多少？

思路：

我们只要关注哪个位置能重复加多少次即可，当然要让更大的数来重复加最多的次数，那么只需要统计有多少个位置可以各自重复加多少次。

     

当然暴力是过不去的。我们需要优化一下。

    
其实就是差分序列思想，先标记都那个地方加，哪个地方减，然后统一前缀和求出最终效果，这就是每个元素出现的次数，然后减去之前的和就行了
 

#include<bits/stdc++.h>     
using namespace std;      
typedef long long ll;
const int N = 1e6 + 5;
int a[N];
ll cnt[N];//前缀和数组，必须开long long
int diff[N];//定义差分数组diff
int n,m,l,r;
ll sum1=0, sum2=0;//原数组和新数组和
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    cin>>m;
    while (m--) {
        cin>>l>>r;
        diff[l]++; //进行差分
        diff[r+1]--;
    }
    for (int i=1; i<=n; i++) { //利用差分数组计算前缀和cnt数组
        cnt[i]=cnt[i-1]+diff[i];
    }
    for (int i=1; i<=n; i++) sum1+=a[i]*cnt[i];
    sort(a+1, a+1+n); 
    sort(cnt+1, cnt+1+n);
    for (int i=1; i<=n; i++) sum2+=a[i]*cnt[i];
    cout << sum2-sum1<< endl;
    return 0;
}