徐妈让我们做一本通的题，说是巩固基础。但说实话这里面的题又烂又水，就连第一章11道题就有双倍经验我也是无语的。
这一章完成时间：两天（其实就是一个晚自习1h+两个中午40min），而且还包括颓废时间
10000.活动安排
贪心区间覆盖经典模型。按照右端点排序，然后依次判断能不能放即可。
struct Edge{
int s,f;
} edge[1005];
int n,ans;
inline bool cmp(Edge x,Edge y)
{
return (x.f==y.f) ? x.s>y.s : x.f<y.f;
}
int main()
{
n=read();
for (int i=1;i<=n;i++) edge[i].s=read(),edge[i].f=read();
sort(edge+1,edge+n+1,cmp);
int last=0;
for (int i=1;i<=n;i++)
{
if (edge[i].s<last) continue;
ans++;
last=edge[i].f;
}
printf("%d",ans);
return 0;
}10001.种树
还是贪心经典模型。按右端点排序，对于每一次询问将不够的树尽量放右端点即可。
struct Edge{
int s,f,sum;
} edge[5005];
bool have_tree[30005];
int n,m,ans;
inline bool cmp(Edge x,Edge y)
{
return (x.f==y.f) ? x.s<y.s : x.f<y.f;
}
int main()
{
n=read(); m=read();
for (int i=1;i<=m;i++) edge[i].s=read(),edge[i].f=read(),edge[i].sum=read();
sort(edge+1,edge+m+1,cmp);
for (int i=1;i<=m;i++)
{
int now=0;
for (int j=edge[i].s;j<=edge[i].f;j++) now+=have_tree[j];
if (now>=edge[i].sum) continue;
now=edge[i].sum-now;
int j=edge[i].f+1;
while (now)
{
j--;
if (have_tree[j]) continue;
have_tree[j]=1;
ans++;
now--;
}
}
printf("%d",ans);
return 0;
}10002.喷水装置
很容易看出，每个圆能覆盖的范围的边界只是与矩形相交的两点连接成的割线。我们已知圆半径 $R$ 和矩形的宽度 $W$ ，那么很容易得出圆心到能覆盖范围边界的距离为 $R^{2} - \left( \dfrac {W}{2}\right) ^{2}$。
这样就得到了每个圆覆盖的左右边界，就可以把这些圆看成线段然后转化成经典的贪心线段全覆盖问题了。按照左端点排序，在每一个左端点 $<=$ 当前已覆盖的最右端点的线段中选一个右端点最大的，直到放到终点。
struct Edge{
double st,ed;
} edge[15005];
int n,l,w,a,b,t;
inline bool cmp(Edge x,Edge y)
{
return (x.st==y.st) ? x.ed>y.ed : x.st<y.st;
}
int main()
{
t=read();
while (t--)
{
int cnt=0,ans=0;
n=read(); l=read(); w=read();
for (int i=1;i<=n;i++)
{
a=read(); b=read();
if (b*2<=w) continue;
double len=sqrt(1.0*b*b-1.0*w*w/4.0);
edge[++cnt].st=a-len;
edge[cnt].ed=a+len;
}
n=cnt;
sort(edge+1,edge+n+1,cmp);
double last=0;
int i=1;
while (i<=n && last<l)
{
double mx=-1;
while (edge[i].st<=last && i<=n)
{
mx=max(mx,edge[i].ed);
i++;
}
if (mx==-1) break;
last=mx;
ans++;
}
if (last<l) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}10003.加工生产调度
那个啥，感觉要解释正确的排序方法感觉有点复杂，我就直接用个洛谷的题解吧： https://www.luogu.org/blog/79017/solution-p1248
struct node{
int a,b,d,id;
} s[1005];
int n,m,ans;
inline bool cmp(node x,node y)
{
return (x.d==y.d) ? (x.d<=0) ? x.a<y.a : x.b>y.b : x.d<y.d;
}
int main()
{
n=read();
for (int i=1;i<=n;i++) s[i].a=read(),s[i].id=i;
for (int i=1;i<=n;i++) s[i].b=read(),s[i].d=(s[i].a==s[i].b) ? 0 : (s[i].a<s[i].b) ? -1 : 1;
sort(s+1,s+n+1,cmp);
int gap=s[1].a,nowb=s[1].b,ans=s[1].b,add=0;
for (int i=2;i<=n;i++)
{
if (s[i].a>=add) s[i].a-=add,add=0;
else add-=s[i].a,s[i].a=0;
if (s[i].a>nowb) gap+=s[i].a-nowb;
else add+=nowb-s[i].a;
nowb=s[i].b;
ans+=s[i].b;
}
ans+=gap;
printf("%d\n",ans);
for (int i=1;i<=n;i++) printf("%d ",s[i].id);
return 0;
}10004.智力大冲浪
很容易想到，肯定要先完成扣款多的，所以我们按照扣款进行排序。而对于每一个可以完成的，我们肯定要把它尽量往后放。
int n,m,ans;
struct node{
int t,w;
} s[505];
bool vis[505];
inline bool cmp(node x,node y)
{
return x.w>y.w;
}
int main()
{
m=read(); n=read();
for (int i=1;i<=n;i++) s[i].t=read();
for (int i=1;i<=n;i++) s[i].w=read();
sort(s+1,s+n+1,cmp);
for (int i=1;i<=n;i++)
{
int j=s[i].t;
while (j && vis[j]) j--;
if (!j) ans+=s[i].w;
else vis[j]=1;
}
printf("%d",m-ans);
return 0;
}10005.数列极差
手算一下可以发现，先算小后算大得到的答案大，先大后小的答案小。
具体的证明我就不推了，不过很显然，加上的每一个1只对后面的答案有贡献，所以后面自然越大越好。
int n,m;
priority_queue <int,vector<int>,greater<int> > q1;
priority_queue <int> q2;
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
m=read();
q1.push(m);
q2.push(m);
}
m=read();
while (!q1.empty())
{
int x=q1.top(); q1.pop();
if (q1.empty())
{
m=x;
break;
}
int y=q1.top(); q1.pop();
q1.push(x*y+1);
}
while (!q2.empty())
{
int x=q2.top(); q2.pop();
if (q2.empty())
{
m=m-x;
break;
}
int y=q2.top(); q2.pop();
q2.push(x*y+1);
}
printf("%d",m);
return 0;
}10006.数列分段
红题。。。这个还用写吗？
int n,m,a;
int main()
{
n=read(); m=read();
int sum=0,cnt=1;
for (int i=1;i<=n;i++)
{
a=read();
if (sum+a<=m) sum+=a;
else cnt++,sum=a;
}
printf("%d",cnt);
return 0;
}10007.线段
与10000重题，垃圾ybt。
struct Edge{
int s,f;
} edge[1000005];
int n,ans;
inline bool cmp(Edge x,Edge y)
{
return (x.f==y.f) ? x.s>y.s : x.f<y.f;
}
int main()
{
n=read();
for (int i=1;i<=n;i++) edge[i].s=read(),edge[i].f=read();
sort(edge+1,edge+n+1,cmp);
int last=0;
for (int i=1;i<=n;i++)
{
if (edge[i].s<last) continue;
ans++;
last=edge[i].f;
}
printf("%d",ans);
return 0;
}10008.家庭作业
看起来和智力大冲浪差不多，但很显然数据范围要大一些，但ybt烂就烂在朴素做法都能得80。
所以我们可以按照时间排序，用优先队列（小根堆）维护，如果能够完成就入队，如果不能完成但价值比队头大就替换掉队头。
struct les{
int t,v;
} s[1000005];
int n,ans;
priority_queue <int,vector<int>,greater<int> > q;
inline bool cmp(les x,les y)
{
return x.t<y.t;
}
int main()
{
n=read();
for (int i=1;i<=n;i++) s[i].t=read(),s[i].v=read();
sort(s+1,s+n+1,cmp);
int t=1;
for (int i=1;i<=n;i++)
{
if (s[i].t>=t)
{
q.push(s[i].v);
t++;
}
else if (s[i].v>q.top())
{
q.pop();
q.push(s[i].v);
}
}
while (!q.empty())
{
ans+=q.top();
q.pop();
}
printf("%d",ans);
return 0;
}10009.钓鱼
这道有点难想，我又没注意到这个小的数据范围，所以看题解前毫无思路。
如果限制了到哪个湖停下来，那么这道题就很容易了。首先走路的时间确定了剩下的时间也就确定了，然后开个优先队列（大根堆），每次取队头元素，计算贡献后减去鱼的减少值再入队，直到了时间耗完了就得到答案了。
因为这道题的数据范围小，所以我们可以枚举在哪个点停下来，最后取一个最大值就行了。
#define pr pair<int,int>
#define mp make_pair
int n,h,ans,t[105],v[105],d[105];
int main()
{
n=read(); h=read()*12;
for (int i=1;i<=n;i++) v[i]=read();
for (int i=1;i<=n;i++) d[i]=read();
for (int i=2;i<=n;i++) t[i]=read();
for (int i=1;i<=n;i++)
{
h-=t[i];
priority_queue <pr> q;
for (int j=1;j<=i;j++) q.push(mp(v[j],d[j]));
int now=0;
for (int j=1;j<=h;j++)
{
pr x=q.top(); q.pop();
if (x.first<=0) break;
now+=x.first;
x.first-=x.second;
q.push(x);
}
ans=max(ans,now);
}
printf("%d",ans);
return 0;
}10010.糖果传递
四倍经验：洛谷P2512 糖果传递、UVa11300、洛谷P4016 负载平衡问题
用 $f[]$ 记录糖果的前缀和，然后枚举断点 $x$ 断环成链，剩下的就按照均分纸牌的思路做，可以得到最小花费为：
$$ans= \sum ^{n}_{i=1}\left| f\left[ i\right] -f\left[ x\right] \right| $$
很显然，$x$ 取中位数时答案最小。
ll n,ans,s[1000005],f[1000005];
int main()
{
n=read();
ll sum=0;
for (int i=1;i<=n;i++) s[i]=read(),sum+=s[i];
sum/=n;
for (int i=1;i<=n;i++) f[i]=f[i-1]+s[i]-sum;
sort(f+1,f+n+1);
int mid=(n+1)>>1;
for (int i=1;i<=n;i++) ans+=abs(f[i]-f[mid]);
printf("%lld",ans);
return 0;
}