题解 P2367 【语文成绩】

学委 · 2018-10-26 18:53:12 · 题解

这道题的输入规模非常大，老师肯定累垮了。

可以普及一下 fread。我之前没学，觉得它一定很复杂，其实它非常单纯。

普通快读

有这样的方法，用它读入整数比 scanf 快，帮你省下时间。

读入一个字符，如果是不是数字就继续读入。

读到一个数字？开始处理：

while(isdigit(ch))//判断是不是数字字符，此函数在头文件<cctype>中
    result = result * 10 + (ch - '0'), ch = getchar();

比如读入数字 408，分成几个字符读入：

发现读入 4，记录 4(变量 result)，读下一个字符。
发现读入 0，先把之前的记录乘以 10，然后加上 0。现在记录了 40，读下一个字符。
发现读入 8，先把之前的记录乘以 10，然后加上 8。现在记录了 408，读下一个字符。
发现读到空格、换行符（标准的数字间隔符）或者 EOF（读不到东西），就可以返回结果：408。

小提示：数字字符要转变为数字，即减去字符 '0'（ASCII码是 48）。

int getint()//名字仿照了getchar()
{
    int res = 0;
    char ch = getchar();
    while(!isdigit(ch))
        ch = getchar();
    while(isdigit(ch))
        res = res * 10 + (ch - '0'), ch = getchar();
    return res;
}

用 fread 优化

只是优化了上面的 getchar()，因为 getchar() 有点慢。

fread 的用处是快速地读入一大堆字符进来，便于你利用这些字符。你肯定知道这个：
```
scanf("%s", a+1);//为了首个字符的下标是1（便于理解），所以读进a+1
//scanf遇到空格、换行符就结束了
```
那么你能理解：
```
fread(tmp+1, 1, 1000000, stdin);
```
迅速读入 1000000 个字符到 tmp 数组。如果没有 1000000 个也不会出错。其中第二个参数是 1：因为 fread 是一块块地读入数据的，这里每块大小定为 1 字节。
一次 fread() 以后，你的 getchar() 可以换成：
```
char getch(){
  return tmp[++cnt];
}
```

只要在原来的快读里面把 getchar() 替换成 getch()，就快了许多了！

fread 讲完了。

细节

为了保证 fread 能读入多于 1000000 个字符，同时 tmp 数组占用的空间也不能太大，我们可以这样修改 getch() ：
```
char tmp[1000010];
int cnt = 0, Max = 0;//两个初值都是0，使第一次getch()一定会调用fread()
char getch()
{
  ++cnt;
  if(cnt > Max)
  {
      cnt = 1;
      Max = fread(tmp+1, 1, 1000000, stdin);
  }
  return tmp[cnt];
}
```
fread() 会返回成功读入的个数，用 Max 记录本次读入了几个（这里限制一次最多 1000000 个），如果 cnt 大于 Max 了，就自动再次 fread() 1000000 个字符。

更多细节，如 getint() 判断负数、fread() 指针写法以及快速输出 fwrite()，感兴趣可看看快读有多难？

原题

先不看题目。

有一个概念叫做前缀和。现在有一个数组 t，里面都是 0。然后，我们用 sum[i] 表示 t 数组前 i 位的和。

如果 t[4] 加上 2，sum 数组要发生什么变化?

sum[4] ~ sum[n] 每一位都要加 2。sum[1] ~ sum[3] 不变。
如果在 t[9] 减去 2，sum 数组发生什么变化?

sum[9] ~ sum[n] 每一位都要减 2。
依次进行上面两步操作以后，sum 数组要发生什么变化?

只有 sum[4] ~ sum[8] 增加 2，其余不变。

如果 t[l] 增加 x，t[r+1] 减去 x，那么 sum[l] ~ sum[r] 都增加 x。

大量的区间加，最后询问所有数中的最小值。

我们可以开一个 t 数组，若修改学生 x ~ y 都加 z，就只在 t 数组上进行两个操作：t[x] 加上 z，t[y+1] 减去 z。你可以脑补出此时有一个 sum 数组，是 t 的前缀和，sum[i] 能正确表示第 i 个学生被修改了多少。但是不要每次修改 sum 数组，而是修改以 t 数组代替。

最后从左到右求一次 t 的前缀和，还原出 sum 数组，加到第 i 位时的 sum 就能表示出这个学生被修改的量。别忘了加上初始成绩，取最小。

t 叫做 sum 的差分数组。t 的前缀和就是 sum。

#include <cstdio>
#include <cctype>
char tmp[1000010];
int cnt = 0, Max = 0;
char getch()
{
    ++cnt;
    if(cnt > Max)
    {
        cnt = 1;
        Max = fread(tmp+1, 1, 1000000, stdin);
    }
    return tmp[cnt];
}
int getint()
{
    int res = 0;
    char ch = getch();
    while(!isdigit(ch))
        ch = getch();
    while(isdigit(ch))
        res = res * 10 + (ch - '0'), ch = getch();
    return res;
}

int n, p;
int a[5000010], b[5000010];
int main()
{
    n = getint(), p = getint();
    for(int i = 1; i <= n; i++)
        a[i] = getint();
    for(int i = 1; i <= p; i++)
    {
        int x = getint(), y = getint(), z = getint();
        b[x] += z;
        b[y+1] -= z;
    }

    int sum = 0, ans = 1000000000;
    for(int i = 1; i <= n; i++)
    {
        sum += b[i];
        if(a[i] + sum < ans)
            ans = a[i] + sum;
    }
    printf("%d\n", ans);
    return 0;
}