苹果（apple）
【题目背景】
尽管题目名是苹果，但是此题和苹果没有任何关系。
这是为什么呢？
【题目描述】
考虑一个树形结构的信号传递网络，初始存在一个信号源点，记其标号为 0。
树上有两种节点，一种为信号中继点，用来接收父亲节点的信号并分发给它的儿子
们。另一种为信号接收点，仅能接收父亲节点的信号但不能向下传递。
对于一个中继点 i ，它能最多将信号分发给 ai 个儿子。对于一个接收点 i，它能生
效仅当它与初始源点间的中继点个数不超过 bi。
对于 bi = 0 的接收点，只能直接连接在源点上。源点可以视作一种特殊的中继点，
它仅能将信号分发给 1 个儿子。
现在给出 n 个中继点和 m 个接收点，小 Z 想知道最多可以使多少个接收点接受到
信号。
注意你不. 一. 定. 需要使用所有 n + m 个节点。
【输入格式】
从文件 apple.in 中读入数据。
输入的第一行包含两个正整数 n, m，保证 1 ≤ n, m ≤ 2 · 105，含义如上所述。
输入的第二行包含 n 个正整数 a1, a2, ..., an，表示 n 个中继点。2 ≤ ai ≤ 2 · 105
输入的第三行包含 m 个正整数 b1, b2, ..., bm，表示 m 个接收点。0 ≤ bi ≤ 2 · 105
【输出格式】
输出到文件 apple.out 中。
输出一行一个正整数，表示最多可以使多少个接收点接受到信号。
【样例 1 输入】
3 6
4 2 2
1 2 3 2 1 1
【样例 1 输出】
5
【样例 2】
见选手目录下的 apple/apple2.in 与 apple/apple2.ans。
【子任务】
测试点 n m 特殊性质
1 ≤ 3 ≤ 3 无
2 ≤ 10 ≤ 10 无
3 ≤ 20 ≤ 20 无
4 ≤ 20 ≤ 20 bi = i
5 ≤ 200000 ≤ 200000 bi 互不相同
6 ≤ 200000 ≤ 200000 ai = 2
7 ≤ 50000 ≤ 50000 无
8 ≤ 200000 ≤ 200000 无
9 ≤ 200000 ≤ 200000 无
10 ≤ 200000 ≤ 200000 无
题解见注释
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int maxn = 2 * 100000 + 10 ; int n,m,a[maxn],b[maxn],ans,now[maxn]; bool cmp(int x,int y){return x>y;} //贪心策略 先放不得不放的接收器 ，在选择分发能力强的中继器 bool judge(int x) { memset(now,0,sizeof(now)); int top(0),flor(1);now[flor]=1; for(;;){ while(x && now[flor] && b[x]<flor) x--,now[flor]--;//如果还有剩余位置，且还有接收七器 if(!x) return true;//如果所有接收器都用了，二分的答案可行； if(x && !now[flor]) return false; //如果还有剩的接收器，且没有剩余位置了，不可行 while(now[flor] && top<n)//统计这层的位置放入中继器，统计下层位置 now[flor+1]+=a[++top],now[flor]--; now[flor+1]+=now[flor];//下层位置加上这层还还剩的位置 flor++; } } int main() { freopen("apple.in","r",stdin); freopen("apple.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i]); sort(a+1,a+1+n,cmp);//从大到小排序 ，贪心得想，二分选的接收器可大的来； sort(b+1,b+m+1,cmp); int l=1,r=m; while(l<r) { int mid=(l+r)>>1; if(judge(mid)) l=mid+1,ans=mid; else r=mid; } cout<<ans<<endl; return 0; }