|
复习时食用，会比较简略。
目录
#10000. 「一本通 1.1 例 1」活动安排
#10001. 「一本通 1.1 例 2」种树
#10002. 「一本通 1.1 例 3」喷水装置
#10003. 「一本通 1.1 例 4」加工生产调度
#10004. 「一本通 1.1 例 5」智力大冲浪
#10000. 「一本通 1.1 例 1」活动安排
题目
题目大意
有n个活动,每个活动i都有起始时间s_i和结束时间f_i。
若区间[s_i,f_i)与区间[s_j,f_j)不相交，则活动i与活动j相容。
选择出由互相兼容的活动组成的最大集合。
1<=n<=1000。
题目分析
贪心。
将每个活动的结束时间从小到大排序。
每次选择结束时间最早的且开始时间大于等于结束时间的活动。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{int s,f;}a[1010];
int cmp(node x,node y)
{
if(x.f==y.f) return x.s<y.s;
else return x.f<y.f;
}
int main()
{
int n; scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].s,&a[i].f);
sort(a+1,a+1+n,cmp);//按结束时间从小到大排序
int ans=1,end=a[1].f-1;
for(int i=2;i<=n;i++)
{
if(a[i].s>end) { ans++; end=a[i].f-1; }
}
printf("%d",ans);
return 0;
}
#10001. 「一本通 1.1 例 2」种树
题目
题目大意
某条街被划为n条路段，每个路段可以种一棵树。
给出了h组建议，希望在路段b到e之间至少要种t棵树。
问至少要种多少棵树。
30%的数据满足0<n<=1000，0<h<=500；
100%的数据满足0<n<3*10^4，h<=5000，0<b<=e<=3*10^4，t<=e-b+1。
题目分析
贪心。
跟上一题有异曲同工之妙。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool b[30010];
struct node{int b,e,t;}a[5010];
int cmp(node x,node y) { return x.e<y.e; }
int main()
{
int n,h; scanf("%d%d",&n,&h);
memset(b,false,sizeof(b));
for(int i=1;i<=h;i++)
{
scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].t);
}
sort(a+1,a+1+h,cmp);//按种树路段的末尾排序
int ans=0;
for(int i=1;i<=h;i++)
{
int s=0;//先找这一段路已有的树
for(int j=a[i].b;j<=a[i].e;j++) if(b[j]) s++;
if(s<a[i].t)//还没有种够
{
for(int j=a[i].e;j>=a[i].b;j--)
{
if(b[j]==false)//这个位置没有树就种啊
{
s++; b[j]=true; ans++;
if(s==a[i].t) break;
}
}
}
}
printf("%d",ans);
return 0;
}
#10002. 「一本通 1.1 例 3」喷水装置
题目
题目大意
长L米，宽W米的草坪里装有n个浇灌喷头。
每个喷头都装在草坪中心线上。
知道每个喷头的位置，以及它能覆盖到的浇灌范围。
问同时浇灌整块草坪最少需要打开多少个喷头？
对于100%的数据，n<=15000。
题目分析
. . “.” . .
. “.” .
“.”
. “.” .
. . “.” . .
带下划线的为半径，“引号”中的是草坪宽。
红色的是能浇灌到的最边上的草坪宽，用kk=sqrt(r*r-(w/2)*(w/2))表示。是美妙的勾股啊！！
则最左边a[s].a=x-kk，最右边a[s].b=x+kk。
如果浇灌的半径*2<草坪宽就不考虑这个喷头，不要问我为什么，或者你告诉我要它有何用。
剩下的水到渠成。
还不懂就看代码吧。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{double a,b;}a[15010];
int cmp(node x,node y) { return x.a<y.a; }
int main()
{
int t; scanf("%d",&t);
while(t--)
{
int n,l,w,s=0; scanf("%d%d%d",&n,&l,&w);
for(int i=1;i<=n;i++)
{
int x,y; scanf("%d%d",&x,&y);
if(y*2<w) continue; s++;
double kk=sqrt(y*y*1.0-w*w/4.0);
a[s].a=x*1.0-kk;//能浇灌到的最边上的最左
a[s].b=x*1.0+kk;//能浇灌到的最边上的最右
}
sort(a+1,a+1+s,cmp);
int d=1,ans=0;
double ll=0;//目前能浇灌到的最边上的草坪的长
bool k=true;
while(ll<l)//革命尚未成功
{
ans++; double maxx=ll;
while(a[d].a<=maxx&&d<=s)
{
ll=max(ll,a[d].b); d++;
//当然是找符合要求且半径长的喷头a
}
if(maxx==ll) { printf("-1\n"); k=false; break; }
}
if(k) printf("%d\n",ans);
}
return 0;
}
#10003. 「一本通 1.1 例 4」加工生产调度
题目
题目大意
n个产品在A、B两个车间加工，必须先在A车间加工后才可以到B车间加工。
产品i在A，B两车间加工的时间分别为 A_i, B_i，安排这 n个产品的加工顺序，使总的加工时间最短。
对于100%的数据，0<n<1000，所有数值皆为整数。
题目分析
？？？没有分析，很迷？？？
一本通上的证明并没有看懂，我太辣鸡了。
反正是这样做的：
设Mi=min(ai,bi)。
将M从小到大排序，若Mi=ai，就将它放在从头开始的作业后面。
反之放在从尾开始的作业前面。
顺序排好了就直接做啊。
代码
#include<cstdio>
#include<cstring>
#include<cstring>
#include<algorithm>
using namespace std;
int s[1010];
struct nod1{int a,b,m,h;}a[1010];
struct nod2{int a,b;}b[1010];
int cmp(nod1 x,nod1 y) { return x.m<y.m; }
int main()
{
int n; scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].a);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].b);
a[i].m=min(a[i].a,a[i].b); a[i].h=i;
b[i].a=a[i].a; b[i].b=a[i].b;
}
sort(a+1,a+1+n,cmp);
int st=1,ed=n;
for(int i=1;i<=n;i++)
{
if(a[i].m==a[i].a) { s[st]=a[i].h; st++; }
else { s[ed]=a[i].h; ed--; }
}
int ans=0,d=0;
for(int i=1;i<=n;i++)
{
d+=b[s[i]].a;
ans=max(d+b[s[i]].b,ans+b[s[i]].b);
}
printf("%d\n",ans);
for(int i=1;i<=n;i++) printf("%d ",s[i]);
return 0;
}
#10004. 「一本通 1.1 例 5」智力大冲浪
题目
题目大意
比赛分为n个时段，每个游戏都必须在t_i前完成，否则从奖励费m元中扣去一部分钱 w_i。
每个游戏能在一个时段内完成，问小伟能赢取最多的钱。
对于100%的数据，有n<=500，1<=t_i<=n。
题目分析
肯定挑钱多的先做啊，需要为什么吗？？？
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool f[250010];
struct node{int time,money;}a[510];
int cmp(node x,node y) { return x.money>y.money; }
int main()
{
int m,n; scanf("%d%d",&m,&n);
memset(f,false,sizeof(f));
for(int i=1;i<=n;i++) scanf("%d",&a[i].time);
for(int i=1;i<=n;i++) scanf("%d",&a[i].money);
sort(a+1,a+1+n,cmp);//按钱的多少排序
for(int i=1;i<=n;i++)
{
bool k=false;
for(int j=a[i].time;j>=1;j--)
{
if(!f[j]) { f[j]=true; k=true; }
if(k) break;
}
if(!k) m-=a[i].money;
}
printf("%d",m);
return 0;
}
| 
转播
