差分-学习经历与例题分享

Word count: 348   |   Reading time≈ 1 min

差分-学习经历与例题分享

我是从这里学习到差分的：

 

No.1 语文成绩;

题目背景

 

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

//这又跟神器有什么关系呢？神说：呵呵。

//因为n和p的范围比较大 建议C++选手使用scanf读入.

//同时建议写读入优化….

//最后一个点，亲测pas读入800+ms，c/C++的scanf 1200+ms，所以这个点的时限改为2s

输入格式

第一行有两个整数n，p，代表学生数与增加分数的次数。

第二行有n个数，a1~an，代表各个学生的初始成绩。

接下来p行，每行有三个数，x，y，z，代表给第x个到第y个学生每人增加z分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

输入输出样例

输入 #1

3 2
1 1 1
1 2 1
2 3 1

输出 #1

2

说明/提示

> 对于40%的数据，有n<=1000 > > 对于60%的数据，有n<=10000 > > 对于80%的数据，有n<=100000 > > 对于100%的数据，有n<=5000000，p<=n，学生初始成绩<=100，z<=100  
 

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>;
using namespace std;
const int MAXN=5000010; 

int    cf[MAXN],//差分数组 
        n,//学生数 
        p;//加分次数 
int main(int argc,const char * argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>p;
    int last=0;
    for(int i=1;i<=n;i++)
    {
    	int in;
    	cin>>in;
    	cf[i]=in-last;
    	last=in;
	}
    while(p--) 
    {
    	int x,y,z;//代表给第x个到第y个学生每人增加z分
        cin>>x>>y>>z;
        cf[x]+=z;
        cf[y+1]-=z;
    }
    int Min=2147483647;
    for(int i=1;i<=n;i++)
    {
    	cf[i]+=cf[i-1];
    	Min=Min<cf[i]?Min:cf[i];
	}
    cout<<Min<<endl;
    return 0;
}

NO.2 积木大赛

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是。

在搭建开始之前，没有任何积木（可以看成n块高度为0的积木）。接下来每次操作，小朋友们可以选择一段连续区间，然后将第第L块到第 R 块之间（含第 块和第 块）所有积木的高度分别增加。

小是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

输入格式

包含两行，第一行包含一个整数n，表示大厦的宽度。

第二行包含n个整数，第i个整数为。

输出格式

建造所需的最少操作数。

输入输出样例

输入 #1

5
 2 3 4 1 2


输出 #1

5


说明/提示

【样例解释】

其中一种可行的最佳方案，依次选择

[1,5] [1,3] [2,3] [3,3] [5,5]

【数据范围】

对于的数据，有1 ≤ n ≤ 10

对于 的数据，有1 ≤ n ≤ 1000

对于 的数据，有1 ≤ n ≤ 100000,0 ≤ h[i]≤ 10000

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n,h[100005],ans;
int main(int argc,const char * argv[]){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++) if(h[i]>h[i-1]) ans+=h[i]-h[i-1];
	cout<<ans<<endl;
	return 0;

No.3 地毯

题目背景

此题约为NOIP提高组Day2T1难度。

题目描述

在 的格子上有 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 。意义如题所述。

接下来 mm 行，每行两个坐标 和 ，代表一块地毯，左上角是 (x1,y1)，右下角是 。

输出格式

输出 行，每行 个正整数。

第 行第 j 列的正整数表示 (i,j)这个格子被多少个地毯覆盖。

输入输出样例

**输入 #1**
5 3
2 2 3 3
3 3 5 5
1 2 1 4
**输出 #1**
0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

数据范围

对于 的数据，有 ，。

对于 的数据，有 。

思路：在输入的矩形范围每行最左，右端加减铺上的地毯个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

int n,m,a,b,c,d;
int mp[1001][1001]; 
int main(int argc,const char * argv[])
{
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b>>c>>d;
for(int j=a;j<=c;j++)
for(int k=b;k<=d;k++)
mp[j][k]++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<mp[i][j]<<" ";
cout<<endl;
}
return 0;
}`

No.4 [USACO07JAN]Tallest Cow S

题目描述：

FarmerJohn 有n头牛，它们按顺序排成一列。 FarmerJohn 只知道其中最高的奶牛的序号及它的高度，其他奶牛的高度都是未知的。现在 FarmerJohn 手上有条信息，每条信息上有两头奶牛的序号（和），其中奶牛的高度一定大于等于奶牛的高度，且a，之间的所有奶牛的高度都比小。现在FarmerJohn想让你根据这些信息求出每一头奶牛的可能的最大的高度。（数据保证有解）

输入格式：

第1行：四个以空格分隔的整数：n，i，h和（和意义见题面; 和 表示第 i 头牛的高度为 h ，他是最高的奶牛）

接下来R行：两个不同的整数和b（1 ≤ a，b ≤ n）

输出格式：

一共n行，表示每头奶牛的最大可能高度.

数据范围：

(1 ≤ n ≤ 10000 ; 1 ≤ h ≤ 1000000 ; 0 ≤ R ≤ 10000)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,bool> ex;
int c[10010],d[10010];
int main(){
    int n,p,h,m;
    cin>>n>>p>>h>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        if(a>b) swap(a,b);
        if(ex[make_pair(a,b)]) continue;
        d[a+1]--,d[b]++;
        ex[make_pair(a,b)]=true;
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+d[i];
        cout<<h+c[i]<<endl;
    }
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2023 Xingzhi

请我喝杯咖啡吧~

支付宝
微信