P2367 语文成绩

题目描述

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

tips：

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

2、因为n和p的范围比较大建议C++选手使用$scanf$读入。

3、同时建议写读入优化….

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

输入输出格式

输入格式

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

第二行有$n$个数，$a_1-a_n$，代表各个学生的初始成绩。

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

输出格式

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

输入输出样例

INPUT #1

OUTPUT #1

说明

对于40%的数据，有$n\leq1000$

对于60%的数据，有$n\leq10000$

对于80%的数据，有$n\leq100000$

对于100%的数据，有$n\leq5000000$，$p\leq n$，学生初始成绩$\leq100$，$z\leq100$

分析

先来看原题：

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

第$x$个到第$y$个学生每人增加$z$分？，区间修改！
果断线段树啊QAQ。

但，

读完题目，我们就会发现只需要在最后求出最小值，并不需要有其他操作

所以线段树这样的算法自然会被pass掉。

而且数据范围：

$$n\leq5000000，p\leq n$$

线段树的数组需要开到segment_tree[maxn<<2]也就是$2e8$左右，绝对会MLE。

算法

自然是差分。

这样$O(n)$的时间复杂度就可以轻松解决了。

代码实现

/* Headers */
#include<cstdio>
#include<cstring>
#include<climits>

/* define */
#define MAXN 5e6+7
using namespace std;
namespace FastIO{
	const int BUFSIZE=(1<<20);
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
	inline char getch(){
		if(is==it)
			it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
		return (is==it)?EOF:*is++;
	}
	inline int getint(){
		int res=0,neg=0,ch=getch();
		while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
			ch=getch();
		if(ch=='-'){
			neg=1;ch=getch();
		}
		while(isdigit(ch)){
			res=(res<<3)+(res<<1)+(ch-'0');
			ch=getch();
		}
		return neg?-res:res;
	}
	inline void write(int x){
    	if(x<0) putchar('-'),x=-x;
    	if(x>9) write(x/10);
    	putchar(x%10+'0');
	}
	inline void space(int x){
		if(x!=0) putchar(' ');
		else putchar('\n');
	}
} 
using namespace FastIO;

/* definitions */
int f[MAXN],diff[MAXN];
int l,r,delta,n,p;
int minx=INT_MAX,sum;

/* functions */

int main(int argc,char *argv[]) {
    #ifndef ltyQwQ's_FILE
    scanf("%d%d",&n,&p);
    for (int i=1;i<=n;i++) scanf("%d",f+i);
    for (int i=1;i<=p;i++){//差分核心代码
        scanf("%d%d%d",&l,&r,&delta);
        diff[l]+=delta;
        diff[r+1]-=delta;
    }
    for (int i=1;i<=n;i++){
        sum+=diff[i];
        minx=min(min,sum+a[i]);
    }
    printf("%d\n",minx);
    #endif
    return 0;
}

再来看一下$tips$:

同时建议写读入优化….

快读/写

直接上代码：

namespace FastIO{
	const int BUFSIZE=(1<<20);
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
	inline char getch(){
		if(is==it)
			it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
		return (is==it)?EOF:*is++;
	}
	inline int getint(){
		int res=0,neg=0,ch=getch();
		while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
			ch=getch();
		if(ch=='-'){
			neg=1;ch=getch();
		}
		while(isdigit(ch)){
			res=(res<<3)+(res<<1)+(ch-'0');
			ch=getch();
		}
		return neg?-res:res;
	}
    inline void write(int x){
    	if(x<0) putchar('-'),x=-x;
    	if(x>9) write(x/10);
    	putchar(x%10+'0');
	}
	inline void space(int x){
		if(x!=0) putchar(' ');
		else putchar('\n');
	}
}

至于$fread$,指点迷津之地。

以下摘自王太阳题解。

namespace FastIO {
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

洛谷P2367题解