更好的阅读体验
题单链接
JC0201. 活动安排
题目大意
有 $n(1 \leq n \leq 1000)$ 个活动，每个活动有开始时间和结束时间，进行一个活动的前提是该活动的开始时间和结束时间的左闭右开区间内没有其他活动，问最多可以进行几个活动
思路
经典贪心题目，按照每个活动的结束时间升序排序，能安排上的活动尽量安排上，边安排边统计答案即可
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1001;
struct A {int l,r;}awa[maxn];
bool cmp(A x,A y) {return x.r<y.r;}
signed main()
{
int n=read(),ans=0,ed=0;
for(int i=1;i<=n;i++) awa[i].l=read(),awa[i].r=read();
sort(awa+1,awa+1+n,cmp);
for(int i=1;i<=n;i++) if(awa[i].l>=ed) ed=awa[i].r,ans++;
write(ans);
return _123hh2;
}
JC0202. 种树
题目大意
有 $n$ 条路段，依次编号为 $1…n$，每个路段最多能种一棵树。现有 $h$ 组种树计划，每组计划有三个整数 $b,e,t$ 表示路段 $b$ 到 $e$ 之间至少种 $t$ 棵树，每组给出的路段区间可以交叉，问满足所有计划至少要种多少棵树
思路
由于路段区间可以交叉，那么我们把一棵树种在交叉区间的贡献值肯定比种在非交叉区间的贡献值大，那么我们可以贪心的将树尽量种在交叉区间上以种最少的树
我们把区间按右端点从小到大排序，对于每个区间来说，从右往左种树是最优选择，因为这样可以使交叉区间利用率更高
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=5e3+1,maxm=3e4+1;
struct A {int l,r,t;}awa[maxn];
bool cmp(A x,A y) {return x.r<y.r;}
bool judge[maxm];
signed main()
{
int n=read(),h=read(),ans=0;
for(int i=1;i<=h;i++) awa[i].l=read(),awa[i].r=read(),awa[i].t=read();
sort(awa+1,awa+1+h,cmp);
for(int i=1;i<=h;i++)
{
int cnt=0;
for(int j=awa[i].l;j<=awa[i].r;j++) if(judge[j]) cnt++;
if(cnt>=awa[i].t) continue;
for(int j=awa[i].r;j>=awa[i].l,cnt!=awa[i].t;j--) if(!judge[j]) judge[j]=1,cnt++,ans++;
}
write(ans),puts("");
return _123hh2;
}
这样做的复杂度最高是 $O(nh)$，数据最大刚好可以跑满
JC0203. 喷水装置
题目大意
一条长 $L$ 米，宽 $W$ 米的草坪上有 $n$ 个浇灌喷头，每个喷头都在草坪中心线上，现给出每个喷头的位置和浇灌半径，问同时教官整块草坪至少要开几个喷头
思路
首先当一个喷头的浇灌半径比 $\frac{W}{2}$ 小时肯定不会开它，因为这样做没有任何贡献
然后观察样例图片我们可以发现对于一个位置在 $x$上，浇灌半径为 $r$ 的喷水装置所能覆盖到的水平上的区间为 $[x-\sqrt{r^2-\frac{W^2}{4}},x+\sqrt{r^2-\frac{W^2}{4}}]$
这样问题就转化成了经典的贪心问题：求用最少的区间覆盖一个长度为 $L$ 的区间
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1.5e4+1;
struct A {double l,r;}awa[maxn];
bool cmp(A x,A y)
{
if(x.l==y.l) return x.r>y.r;
return x.l<y.l;
}
signed main()
{
int t=read();
while(t-->0)
{
int n=read(),l=read(),cnt=0,ans=0,flg=0;
double w,now=0;cin>>w;w/=2.0;
for(int i=1;i<=n;i++)
{
double x,r;cin>>x>>r;
if(r<=w) continue;
awa[++cnt].l=x-sqrt(r*r-w*w);
awa[cnt].r=x+sqrt(r*r-w*w);
}
sort(awa+1,awa+1+cnt,cmp);
if(awa[1].l>now) {puts("-1");continue;}
for(int i=1;i<=cnt;)
{
double rr=now;
while(awa[i].l<=now&&i<=cnt) rr=max(rr,awa[i].r),i++;
if(rr==now) {i++;continue;}
now=rr,ans++;
if(now>=l) {flg=1;break;}
}
if(flg) write(ans),puts("");
else puts("-1");
}
return _123hh2;
}
JC0204. 加工生产调度
题目大意
有 $n$ 个工件要加工，每个工件需要在 $A,B$ 车间加工两次且必须先在 $A$ 车间加工，再在 $B$ 车间加工，每个工件都有自己的加工时间 $A_i,B_i$，求加工完所有工件的最小时间
思路
我们发现加工完所有工件的最后时刻一定是 $B$ 车间在加工，所以我们要尽可能使 $B$ 车间的工作是连续的
我们发现 $A$ 车间的加工必然是连续的，为了使 $B$ 车间尽快开工，我们可以选择在 $A$ 车间加工时间最短并必须在 $B$ 车间加工时间比在 $A$ 车间加工时间长的最长的那个工件
这样我们可以利用 $A_i$ 到 $A_i+B_i$ 这段时间来在 $A$ 车间加工更多的工件，使得 $B$ 车间尽可能连续进行加工
考虑将每个工件按 $A_i-B_i$ 进行分组
- $A_i<B_i$
- $A_i=B_i$
- $A_i>B_i$
对于第一组来说，我们应该按 $A_i$ 从小到大排序的同时 $B_i$ 从大到小排序，这样可以使 $B$ 车间尽可能连续进行加工
对于第二组来说，我们按 $A_i$ 从大到小排序，原理同第三组的分析
对于第三组来说，我们此时理想状态下应该是 $B$ 车间仍在加工，$A$ 车间正好加工完的状态，我们发现，加工第三组能得到的最坏的情况是加工完 $A$ 车间最后一个工件，才在 $B$ 车间加工刚才那个工件，所以我们尽可能让最小的 $B_i$ 最后加工
这样我们可以用最少的时间来加工完所有的工件
最后统计答案只需要扫一遍排完序后的工件，模拟即可
事实上，这种调度方法叫做Johnson法则，可以看看网上一些巨佬的数学证明，我太菜了不会证
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e3+1;
int arra[maxn],arrb[maxn];
struct A {int a,b,id;}awa[maxn];
struct B {int a,b,id;}qwq[maxn];
bool cmp1(A x,A y) {return x.a<y.a;}
bool cmp2(B x,B y) {return x.b>y.b;}
signed main()
{
int n=read(),a=0,b=0,cnt1=0,cnt2=0;
for(int i=1;i<=n;i++) arra[i]=read();
for(int i=1;i<=n;i++) arrb[i]=read();
for(int i=1;i<=n;i++)
{
int x=arra[i],y=arrb[i];
if(x<y) awa[++cnt1].a=x,awa[cnt1].b=y,awa[cnt1].id=i;
else qwq[++cnt2].a=x,qwq[cnt2].b=y,qwq[cnt2].id=i;
}
sort(awa+1,awa+1+cnt1,cmp1);sort(qwq+1,qwq+1+cnt2,cmp2);
for(int i=1;i<=cnt1;i++)
{
if(a+awa[i].a>b) a+=awa[i].a,b=a+awa[i].b;
else a+=awa[i].a,b+=awa[i].b;
}
for(int i=1;i<=cnt2;i++)
{
if(a+qwq[i].a>b) a+=qwq[i].a,b=a+qwq[i].b;
else a+=qwq[i].a,b+=qwq[i].b;
}
write(b),puts("");
for(int i=1;i<=cnt1;i++) cout<<awa[i].id<<" ";
for(int i=1;i<cnt2;i++) cout<<qwq[i].id<<" ";cout<<qwq[cnt2].id;
return _123hh2;
}
JC0205. 智力大冲浪
题目大意
给一个初始钱数 $sum$ 和 $n$ 个任务，每个任务都有截至期限 $t_i$ 和价值 $w_i$，每个单位时间都可以完成一个任务，未完成的任务将会在 $sum$ 中扣去相应价值，求 $sum$ 的最大值
思路
贪心，我们把钱最多的先做了，剩下的实在做不了的任务的总扣款数额一定是最少的
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=501;
bool flg[maxn];
struct A {int t,w;}awa[maxn];
bool cmp(A x,A y) {return x.w>y.w;}
signed main()
{
int sum=read(),n=read(),now=0;
for(int i=1;i<=n;i++) awa[i].t=read();
for(int i=1;i<=n;i++) awa[i].w=read();
sort(awa+1,awa+1+n,cmp);
for(int i=1;i<=n;i++)
{
int f=0;
for(int j=awa[i].t;j>=1;j--) if(!flg[j]) {flg[j]=1,f=1;break;}
if(!f) sum-=awa[i].w;
}
write(sum);
return _123hh2;
}
JC0206. 纪念品分组
题目大意
给出 $n$ 个纪念品，每个纪念品都有对应的价格 $P_i$，现将纪念品分组，每组最多装两个纪念品，并且两个纪念品的价值之和不得超过给定的数 $w$，求纪念品最少可以分为多少组
思路
又是一道经典的贪心，我们一定是尽可能将纪念品两两配对组装才能使分的组最少
很容易想到最大的和最小的装在一起，若价值之和超过 $w$，那么最大的那个纪念品一定是单独一组的
所以我们可以对数组进行排序，然后用双指针来模拟纪念品的分组操作即可
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=3e4+1;
int awa[maxn];
signed main()
{
int w=read(),n=read(),ans=0;
for(int i=1;i<=n;i++) awa[i]=read();
sort(awa+1,awa+1+n);
int l=1,r=n;
while(l<=r)
{
if(l==r) {ans++;break;}
if(awa[l]+awa[r]>w) ans++,r--;
else l++,r--,ans++;
}
write(ans);
return _123hh2;
}
JC0207. 数列分段
题目大意
给定一个长度为 $n$ 的正整数数列 $A_i$，现将其分为连续的若干段，每段和不超过 $M$，问最少能分为多少段
思路
贪心，只需要从前往后遍历数组并统计当前访问过的数的总和，若比 $M$ 大，则答案加一，总和归零
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
signed main()
{
int n=read(),m=read(),sum=0,ans=1;
for(int i=1;i<=n;i++)
{
int x=read();
if(sum+x>m) sum=x,ans++;
else sum+=x;
}
write(ans);
return _123hh2;
}
JC0208. 线段
题目大意
有 $n$ 条线段，选其中 $k$ 条线段使这 $k$ 条线段两两没有重合部分，求 $k$ 最大为多少。
思路
这跟JC0201. 活动安排的思路一样的，只是换了个问法而已
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e6+1;
struct A {int l,r;}awa[maxn];
bool cmp(A x,A y) {return x.r<y.r;}
signed main()
{
int n=read(),ans=0,ed=0;
for(int i=1;i<=n;i++) awa[i].l=read(),awa[i].r=read();
sort(awa+1,awa+1+n,cmp);
for(int i=1;i<=n;i++) if(awa[i].l>=ed) ed=awa[i].r,ans++;
write(ans);
return _123hh2;
}
JC0209. 家庭作业
题目大意
给出 $n$ 份作业，每份作业都有它的期限 $t$ 和学分 $w$，每天只能写一份作业，问最终能得到至多多少学分
思路
这与JC0205. 智力大冲浪的思路是一样的，但是我们发现数据范围变得很大，按原先的算法会T飞，我们需要一种时间复杂度更小的算法来求出目前的作业是否能完成
用数组 $pre$ 来维护每个时间点的前继最大空闲时间点，考虑用并查集维护，复杂度 $O(nlog*(maxn)$ ，其中 $maxn$ 是期限 $t$ 的最大值
代码
#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e6+1;
int pre[maxn];
int find(int x) {return x==pre[x]?x:pre[x]=find(pre[x]);}
struct A{int t,w;}awa[maxn];
bool cmp(A x,A y){return x.w>y.w;}
signed main()
{
int n=read(),ans=0,maxx=0;
for(int i=1;i<=n;i++) awa[i].t=read(),awa[i].w=read(),maxx=max(maxx,awa[i].t);
for(int i=1;i<=maxx;i++) pre[i]=i;sort(awa+1,awa+1+n,cmp);
for(int i=1;i<=n;i++)
{
int x=find(awa[i].t);
if(x) ans+=awa[i].w,pre[x]=x-1;
}
write(ans);
return _123hh2;
}
JC0210. 钓鱼
题目大意
有 $n$ 个湖，每个湖你都可以钓鱼，每个湖在开始都会钓到 $x$ 条鱼，此后每 5 分钟都会减少 $D_i$，钓上来的鱼的数量不会为负数，从第 $i$ 个湖到第 $i+1$ 个湖会花费 $5* T_i$ 分钟，你有 $H$ 小时空闲时间来钓鱼，问最后能钓到的鱼的最大数量
思路
注意到每个鱼塘能钓到的鱼的数量是一定的
我们可以对湖进行枚举，然后求我们走到第 $i$ 个湖时钓到的最大的鱼的数量
代码
#include<bits/stdc++.h>
#define int long long
#define _123hh2 0
#define in inline
#define ri register
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
void write(int x) {if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e6+1;
struct A{int f,d;}awa[101];
int w[101],qwq[maxn];
signed main()
{
int n=read(),h=read()*60,cnt=0,ans=0;
for(int i=1;i<=n;i++) awa[i].f=read();
for(int i=1;i<=n;i++) awa[i].d=read();
for(int i=2;i<=n;i++) w[i]=read()*5;
for(int i=1;i<=n;i++)
{
h-=w[i];int sum=0;
if(h<0) break;
for(int j=h;j&&awa[i].f;j--) qwq[++cnt]=awa[i].f,awa[i].f-=awa[i].d,awa[i].f=max(awa[i].f,0ll);
sort(qwq+1,qwq+1+cnt);
for(int j=cnt,k=h;j&&k;j--) k-=5,sum+=qwq[j];
ans=max(ans,sum);
}
write(ans);
return _123hh2;
}
JC0211. 糖果传递
题目大意
$n$ 个人围一圈，每人都有 $a_i$ 个糖果，每人的糖果只能左右传递，每次传递一颗糖视为一次操作，求每个人的糖都相等的最小操作数
思路
我们先求出来每个人最后分到的糖果数，然后设一个数组 $give_i$ 表示第 $i$ 个人向右给出的糖果，$give_i$ 为负数时说明第 $i$ 个人向左给出糖果
那么操作数就是 $give$ 数组绝对值的和
我们可以得到如下式子
$a_1 + give_n -give_1 = avg$
$a_2 + give_1 -give_2 =avg $
$…$
$an + give{n-1} -give_n = avg $
不难看出有规律 $ai + give{i-1} - give_i = avg$
移项得 $givei=give{i-1} + a_i - avg$
而 $give{i-1} = give{i-2} + a_{i-1} - avg$
迭代并带入得 $givex = \sum\limits{i=1}^{x-1} a_i - (x-1)*avg + give_1(2 \leq x \leq n)$
对于 $\sum\limits_{i=1}^{x-1} a_i - (x-1)*avg $，我们可以用前缀和数组 $qzh$ 维护
得
$give_i=give_1 + qzh_i$
将 $qzh$ 的数取相反数，得 $give_i=give_1 - qzh_i$
发现这时候我们要求的操作总数为 $|give1|+|give_1 -qzh_1| + … + |give_1 - qzh{n-1}|$
不难发现使总数最小的方案为 $give_1$ 为 $qzh$ 数组的中位数
代码
#include<bits/stdc++.h>
#define int long long
#define _123hh2 0
#define in inline
#define ri register
using namespace std;
in int read()
{
int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
void write(int x) {if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e6+1;
int awa[maxn],qzh[maxn];
signed main()
{
int n=read(),avg=0,ans=0;
for(int i=1;i<=n;i++) awa[i]=read(),avg+=awa[i];
avg/=n,qzh[1]=-avg;
for(int i=1;i<n;i++) qzh[i]=qzh[i-1]+avg-awa[i];
sort(qzh+1,qzh+n);qzh[0]=0;
for(int i=1;i<=n;i++) ans+=abs(qzh[n/2]-qzh[i-1]);
write(ans);
return _123hh2;
}
