差分与前缀和2
差分
T1 车票
题目：
考虑一条高铁线路 G39，这条线路依次经过 N 个火车站，编号为 1，2，3，……，n。
现在你得到了关于未来 K 天的 M 条订票信息，问你每天至少安排多少个座位可以满足这些订票信息。
每条订票信息形如 i j k, 代表在第 i 天出行，从 j 火车站上车，从 k 火车站下车。
注意座位可以重复使用，但不能两个人坐一个座位，如果一条信息是1 1 3，另一条信息是 1 3 5，那么只安排一个座位即可 (第一位乘客在 3 号火车站下车，同时第二位乘客在 3 号火车站上车)。
输入
第一行三个整数 N,M,K。
接下来 M 行，每行三个整数 i j k，意义见题目描述。
输出
K 行，每行一个整数，表示当天至少需要安排多少个座位。
输入样例
10 5 3
1 1 3
1 3 5
2 1 4
1 7 8
2 2 10
输出样例
1
2
0
思路：
这道题目很明显要用差分来做，每次把乘客日期标注一下，上车站点+1，下车站点-1，然后分日期做前缀和，把当天的最大值求出来输出就好了，但是我一开始犯了一个低级错误，导致我做错之后找了很久才找到错误点，后面又因为各种输出问题导致超时。
第一次： 把n打成m可还行（第三次for）
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int d,l,r;
cin>>d>>l>>r;
insert(d,l,r);//差分函数
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]+=a[i][j-1];
if(a[i][j]>b[i])
b[i]=a[i][j];
}
}
for(int i=1;i<=k;i++)
cout<<b[i]<<endl;
第二次： ios语句竟然对scanf没用
ios::sync_with_stdio(false);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
int d,l,r;
scanf("%d%d%d",&d,&l,&r);
insert(d,l,r);
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]+=a[i][j-1];
b[i]=max(b[i],a[i][j]);
}
}
for(int i=1;i<=k;i++)
cout<<b[i]<<endl;
return 0;
}
第三次： 删scanf的时候不小心把ios删了。
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int d,l,r;
cin>>d>>l>>r;
insert(d,l,r);
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]+=a[i][j-1];
b[i]=max(b[i],a[i][j]);
}
}
for(int i=1;i<=k;i++)
cout<<b[i]<<endl;
第四次： 要把b[i]放到前一个循环输出减少时间。
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int d,l,r;
cin>>d>>l>>r;
insert(d,l,r);
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]+=a[i][j-1];
b[i]=max(b[i],a[i][j]);
}
}
for(int i=1;i<=k;i++)
cout<<b[i]<<endl;
代码（正解）：
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[50][1000010],b[100],c[100];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int d,l,r;
cin>>d>>l>>r;
a[d][l]++;
a[d][r]--;
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]+=a[i][j-1];
b[i]=max(b[i],a[i][j]);
}
cout<<b[i]<<endl;
}
return 0;
}
今天把这件事花大篇幅写在这里，是希望能记住血的教训，以此铭记！！！！！！
前缀和
T2 最少反转
题目：
小b现在收到一个任务：给他一个长度为 n 的 01 序列，每次可以翻转其中一个将其从1变为0或者从0变为1，要求翻转完成后序列不降，请问最少需要翻转多少次？
输入
第一行一个整数n （1≤n≤20000）
第二行是一个由‘0’和‘1’组成的字符串。
输出
一个整数，表示最少翻转次数。
输入样例
6
010110
输出样例
2
思路：
一开始做这道题的时候我的思路是把所有降序的数字找出来，然后输出个数，但是这不对，我又陷入了思维死局，一直找不到正确的方法，后来还是老师提醒了我思路，我才做出来了，这道题目的做法：因为这个序列只有0和1，而且要求不降，那么其实我们求出1的个数就行了，用前缀和标记从第一位到第i位1的个数就行了，然后因为它还要求是最少的，所以我们还得比较一下，找到最小的。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[20010],h=20000;
char s[20010];//用字符数组是因为字符串强制从第0位开始，不方便标记。
int main()
{
cin>>n;
scanf("%s",s+1);
int k=0,t=0;
for(int i=1;i<=n;i++)
{
a[i]=a[i-1];
if(s[i]=='1')
a[i]++;
}
for(int i=1;i<=n;i++)
h=min(h,a[i-1]+n-i+1-a[n]+a[i-1]);
cout<<h;
return 0;
}
T3 小b的魔法
题目：
小b是走读生，每天上学都要走过 n 个路口才能到达学校，通过每两个路口都要花费一定的时间 t 。尽管家和学校有可能相距非常远，但是小b风雨无阻，每天按时上学。
最终他的坚持感动了god，在一天电闪雷鸣之后，小b竟然拥有了一个魔法，它的转移半径为 r，也就是说可以瞬间从一个路口 i 转移到 i+r 或者 i-r 的路口，为了不滋生他的懒惰之心，这个魔法只能用一次。
请问为了尽快到达学校，小b所花费的最少时间是多少？
注意：转移不花时间，如果转移后已经超过了学校，那么认为已经到达
输入
第一行n,r。
第二行n-1个整数，表示通过每两个相邻的路口的时间。
输出
一个整数。
输入样例
4 2
3 5 1
输出样例
1
【数据规模】
2<=n,r<=10^6, 1<=t<=10^12
思路：
这道题目是一道前缀和的题目，我一开始想了半天，然后想到了解法：要找到最少的时间，那么就要使得他转移的路口是r个连续的、加起来花费时间最久的，但是要注意一个问题，这道题目一个路口最久要花费10^12也就是一万亿，而且最多还会有10 ^ 6，一百万个路口，加起来大概有10 ^18，那么用int连一个路口都存不下，long long也可能不够，所以要用unsigned long long来存。
代码：
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,a[1000010],s[1000010];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
unsigned long long lz=s[m];
for(int i=m;i<n;i++)
lz=max(lz,s[i]-s[i-m]);
cout<<s[n-1]-lz;
return 0;
}
想到思路后还挺好写的
转载：https://blog.csdn.net/SSL_wyd/article/details/113445980