题目描述
小 A 的工厂接到了一个大客户的订单，为了展示自己工厂的实力，小 A 需要尽可能快的完成这一批订单。
工厂里，一共有 n 个车床，编号分别为 1,2,…,n，从左到右依次排列。由于这些车床的出厂批次不同，i 号车床最多只能生产 c_i 种零件。现在需要加工 m 种零件，零件编号为 1,2,…,m，其中零件 i 需要被一段连续的车床加工，形式化的说，需要的车床就是一个区间 [a_i,b_i]。
小 A 想知道对于这 m 种零件，在不超过每个车床承载量的情况下，工厂最多可以同时生产的零件种数。
输入
第 1 行，输入两个空格隔开的整数，n 和 m。
接下来输入有 n 行，其中第 i+1 行，输入一个整数 c_i，表示 i 号车床最多能够生产的零件种类数。
接下来输入有 m 行，其中第 n+1+i 行，输入两个空格隔来的整数 a_i,b_i，含义同题面。
输出
输出一个整数，表示工厂最多可以同时生产的零件种数。
样例输入
5 4
1
3
2
1
3
1 3
2 5
2 3
4 5
样例输出
3
思路
贪心思路：先尝试每个零件都生产，答案初始为m，利用差分和前缀和，可以判断第i车床可以生产零件种数还差多少。
从左到右扫描， 遇到第一个可加工零件种数少于需要加工零件数量，意味着要少加工一些零件，这里就可以贪心的选择后续影响最远的零件去掉（去掉任意一个零件都算少一个，肯定选后续影响最长的）。
具体操作的时候，先按零件区间l从小到大排序，逐个做差分，同时将r放到大根堆里，当遇到必须去掉零件时，弹出堆顶，逆着做差分（抵消掉之前的影响），答案数减1。
using namespace std;typedef long long ll;const int M=100005;int n,m,a[M],s[M],ans;struct node{int l,r;}p[M];priority_queue<int,vector<int>,less<int> >q;bool cmp(node x,node y){return x.l<y.l;}int main(){scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) scanf("%d",&a[i]);for(int i=1; i<=m; i++){scanf("%d%d",&p[i].l,&p[i].r);s[p[i].l]++;s[p[i].r+1]--; //差分}sort(p+1,p+1+m,cmp);ans=m;for(int i=1,j=1; i<=n; i++){s[i]+=s[i-1]; //前缀和while(j<=m && p[j].l<=i){q.push(p[j].r);j++;}while(a[i]<s[i]){int x=q.top(); q.pop();s[i]--;s[x+1]++; //抵消之前的差分ans--;}}printf("%d",ans);return 0;}
