先来落实比较简单的T3,T4
T3 团结的队伍 team
题目描述
众所周知,长郡信息组是一个团结友爱的优秀团队。为了弘扬团队精神,践
行*核心价值观,秉承朴实沉毅的校训,信息组决定外出游玩(。。。。。。)。
jump:“你们想怎么玩?”
xzy:“要组队一起走。”
XYK:“我喜欢 2 个人组一队。”
LCF:“我太犇了,我要一个人走。”
llg:“Please call me Captain Farmer. I ‘ll lead the way ~”
LRH:“jump is a code farmer.”
dyc:“我要跟遥遥一起走~”
jump:“那我就写一个程序来帮你们分组~”
假设 cj 中学有 n 名 oier,每个人都有一个被称为“犇气”的数值,我们需要为
出去游玩的 cjoier 进行组队,每支队伍最多两个人(不要问我为什么是两个人)。
但是科学家发现,如果两只神犇呆在一起,他们的“犇气”就会发生剧烈的化学反
应,威胁世界和平。为了世界和平与中国的可持续发展,每支队伍的“犇气”之和
不能超过 C。现在 jump 要去屠题,没空解决这个问题,所以请你帮他求出信息
组最少需要组建多少支队伍。
输入数据
第一行包含两个数 n,C;分别表示人数和每支队伍的犇气上限。
接下来 n 行,每行一个数 ai,表示每个人的“犇气”值
输出数据
仅包含一个数,表示最小队伍数
输入样例
6 12
7 2 9 3 7 6
输出样例
4
数据规定
对于 30%的数据,1<=n<=1000
对于 100%的数据,1<=n<=300000,ai<=c 且保证 ai、c 均在 int 范围内。
思路:
这题实在是送分题,贪心入门题,类似我们做过的人过和....
我们把数据输入后,把这些数据按犇值排一遍序
然后我们设置一个头指针和尾指针,按照贪心的思想,我们要把犇值最大的和最小的相搭配;
如果2人的犇值之和大于最大值,我们就把尾指针向前移一个,同时sum++,相当于那个犇值较大的单独一个队;
如果2人犇值之和小于最大值,那么头指针向后移,尾指针向前移(题目规定最多2人一队)
输出
直接输出统计的sum
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int a[300010];
int sum=0;
int scan()
{
int as=0,fin=1;
char c=getchar();
while(c<'0'||c>'9'&&c!='-') c=getchar();
if(c=='-') fin=-1;
while(c>='0'&&c<='9')
{
as=(as<<3)+(as<<1)+c-'0';
c=getchar();
}
return as*fin;
}
int main()
{
freopen("team.in","r",stdin);
freopen("team.out","w",stdout);
n=scan();
m=scan();
int head=1,tail=n;
for(int i=1;i<=n;i++)
{
a[i]=scan();
}
sort(a+1,a+n+1);
while(head<=tail)
{
if(head==tail) sum++,head++,tail--;
else if(a[head]+a[tail]<=m) ++sum,head++,tail--;
else if(a[head]+a[tail]>m) ++sum,tail--;
}
cout<<sum;
return 0;
}
/*
思路:
这题好像是贪心啊....
那么我们就sort一下
然后最大的和最小的匹配一下就可以了??
试试大样例吧
*/
代码在这里
T4 llg 的农场
题目描述
llg 是一名快乐的农民,他拥有一个很大的农场,并且种了各种各样的瓜果蔬菜,到了每年秋天,他就可以把所有蔬菜水果卖到市场上,这样他就可以获利。但今年他遇到了一个难题——有许多鸟来到了他的农场偷吃他的瓜果蔬菜。不知所措的 llg 只好求助于 jump,万能的 jump 于是给了 llg 一些稻草人(据说可以驱鸟)。每个庄稼都可以看做是坐标系里面的一个点,当它处于某个稻草人的范围内时就可以视为被保护。可是每个稻草人的辐射范围有限,根据测定,每个稻草人的辐射范围都是一个半径为 R 的圆,如下图:
llg 很懒,所以他只打算把稻草人放在坐标系的 x 轴上,而任何庄稼(x,y)都满足 y>0。图中的小红点就是庄稼,蓝点即稻草人放的位置。现在请你来帮助 llg设计一个方案,用尽可能少的稻草人来保证所有庄稼都是安全的。若存在无法覆盖的庄稼或者 jump 给的稻草人不够覆盖所有庄稼,请输出-1。
输入数据
每个测试点含多组数据
每组数据第一行包含 n,R,C;分别表示庄稼的数量、稻草人的最大覆盖半径,命题人:黎锦灏
稻草人的数量。
接下来 n 行,每行包括两个数 xi,yi 表示一个点的坐标
输入以“0 0 0”结尾
输出数据
对于每组数据,请输出最小要用多少稻草人,才能保证覆盖所有庄稼。若无法覆
盖或数量不够,请输出-1。
输入样例
3 2 3
1 2
-3 1
2 1
3 2 4
1 3
-3 1
2 2
0 0 0
输出样例
2
-1
数据规定
对于 30%的数据,1<=n<=3000
对于 100%的数据, 1<=n<=50000,1<=数据组数<=10,其余数据均保证不会超过 int
的范围
思路:
solution说"这道题是用来 send meat 的水题。。。我也不知道这道题有什么部分分是可
以拿的。。。"
我也无语了.......
有数学知识可知
图中 ABCD 为庄稼的位置。假设稻草人半径为 2,那么能够覆盖 A 点(1,1)的
稻草人一定处在以 A 为圆心,R 为半径的圆与 x 轴的两个交点之间。
所以原题就转化了,我们现在的问题就是使每个区0间内有一个"圆心";
然后我们就储存每个区间的左端点和右端点
然后以左端点或右端点为依据来进行排序
如果是以最左端排序,那么我们就保存最小的右端点,如果有区间的左端点大于右端点
我们就对其进行更新,ans++;
输出
输出ans就可以了
代码待会贴上来