牛客练习赛34的C、D题题解

学到了前缀和,开心

C题

题目描述 
小w有m条线段，编号为1到m。
用这些线段覆盖数轴上的n个点，编号为1到n。
第i条线段覆盖数轴上的区间是L[i]，R[i]。
覆盖的区间可能会有重叠，而且不保证m条线段一定能覆盖所有n个点。
现在小w不小心丢失了一条线段，请问丢失哪条线段，使数轴上没被覆盖到的点的个数尽可能少，
请输出丢失的线段的编号和没被覆盖到的点的个数。
如果有多条线段符合要求，请输出编号最大线段的编号（编号为1到m）。

输入描述:
第一行包括两个正整数n，m(1≤n，m≤10^5)。
接下来m行，每行包括两个正整数L[i]，R[i](1≤L[i]≤R[i]≤n)。
输出描述:
输出一行，包括两个整数a b。
a表示丢失的线段的编号。
b表示丢失了第a条线段后，没被覆盖到的点的个数。

输入

5 3
1 3
4 5
3 4

输出

3 0

这里涉及到区间的修改与查询.先了解一下差分区间和前缀和:如果要修改[L, R]区间,可以直接将区间
L[i] + k,R[i + 1] - k,然后遍历一遍数组，将前缀和d[i] += d[i - 1]与原数组相加,最后就可以得到修改后的数组。
例如0 1 2 3 4 5 0, 我这里想把[2, 4]区间里面的值都加上1，将[1, 3]中的值都加上3,
得到的差分区间为0 3 1 0 -3 -1 0,
然后遍历数组，将前缀和(0 3 4 4 1 0 0)与原数组相加得到0 4 6 7 5 5 0.这样的好处是只需要一次遍历就能修改所有改变了的值。
然后回到这题：首先对输入的区间进行一次差分d[L[i]]++, d[R[i] + 1]–，然后使用前缀和
d[i] += d[i - 1]
得到更改之后的数组(因为初始数组内的数字全为0)。将数组内值为1的点找出来(因为覆盖的点的个数
为1，那么删除该线段之后，该点就没有被覆盖了)，再用一次前缀和，这个前缀和就是便于查找某区间
内点的个数为1的数组，同时在遍历的时候记录值为0的点,即线段没覆盖的点cnt，最后用求得的前缀和
数组便可以找到区间内覆盖点的数目最少的区间以及个数min, cnt + min就是没被覆盖的点的个数。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100001;
int main(){
    int L[N], R[N];
    int b[N], s[N];
    memset(b, 0, sizeof(b));
    memset(s, 0, sizeof(s));
    int n, m, cnt = 0;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> L[i] >> R[i];
        b[L[i]]++;
        b[R[i] + 1]--;
    }
    for(int i = 1; i <= n; i++){
        b[i] += b[i - 1];
        s[i] = s[i - 1] + (b[i] == 1);
        cnt += (b[i] == 0);
    }
    int now = 0, min = 1000000, ans = 1;
    for(int i = 1; i <= m; i++){
        now = s[R[i]] - s[L[i] - 1];
        if(now <= min){
            min = now;
            ans = i;
        }
    }
    cout << ans << " " << min + cnt << endl;
    return 0;
}

D题

题目描述
旅行到K国的小w发现K国有着很多物美价廉的商品，他想要买一些商品。

结果一掏钱包，包里只剩下n张K国的纸币了，说起来也奇怪，K国纸币并不像其他国家一样都是1元，5元，10元…
而是各种奇怪的面值，所以找零就不是很方便。 已知商店里的商品价格都是小于等于m的正整数，如果有可能存在
某个商品的价格为x<=m并且x无法在不找零的情况下支付，小w就不能任意购买一件商店中的商品，
小w想知道自己在不找零的情况下能否任意购买一件商店中的商品，你能帮帮他么？

输入描述:
第一行是两个正整数n,m（n<=1000,m<=2^31-1）
第二行共n个正整数ai(1<=ai<=2^31-1)，代表小w钱包中K国纸币的面值。
输出描述:
如果能任意购买商店中的物品，请输出"YES"(不含引号)。
如不能任意购买商店中的物品，请输出"NO"（不含引号）。

输入

4 10
1 2 3 4

输出

YES

商品价值和纸币面值>=1,首先将纸币面值排序，第一个数必须为1，否则不能购买商店中的商品,第二个
数为1或2，否则不能凑成2; 第三个数为1、2或3，否则不能凑成3，以此类推. 数列{an}满足题意,
该数列是从1开始表示一直到最大能表示的数，也就是数列的和Sn， 数列的第一个数为a[0],
将后面的数一个个加入到该数列中,加入的条件为 a[i + 1] <= sum + 1，如何理解呢，
首先：a[i + 1] 如果大于sum + 1，那么该数列只能表示1~sum和a[i + 1] + {1 ~ sum}，
无法表示sum + 1; 如果等于那么a[i + 1]本身就可以 表示sum + 1; 如果小于，
a[i + 1] + {1 ~ sum}表示的范围就是{1 ~ sum + a[i + 1]}, a[i + 1]又至少为1，则必定满足。最后判断表示最大数的sum大于等于m，那么就输出YES，否则NO.

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
 
int main(){
    ll n;
    ll m, a[1001];
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
   sort(a + 1, a + n + 1);
   ll sum = 0;
   for(int i = 0; i <= n; i++){
       sum += a[i];
       if(a[i + 1] > sum + 1)
           break;
   }
   if(sum >= m)
       cout << "YES" << endl;
   else
       cout << "NO" << endl;
    return 0;
}