首先看到这一道题,注意到N很小,最多只有100,所以首先想到的是简单粗暴的模拟算法。因为数据是无序的,而模拟算法都需要使用到有序的,所以要先排序。模拟算法的思路大致如下,从每一个草堆出发,让其它的草堆爆炸,每一个节点最多可以接触到所有的节点,故时间复杂度为O(N^2)。可以证明,如果向左扩张,让左边的草堆爆炸,产生的冲击波最多能够达到原来的出发点的右边一个坐标,再向左爆炸,产生的冲击波同样最多也只能到出发点右边的一个坐标,所以从一个点出发,不需要让每一次爆炸都考虑两边爆炸会让哪些炸掉。向右边扩张同样是这样。得到这个结论,就不需要用宽搜把每一个点都向左右扩张,只需要向单个方向考虑。题目描述
牛奶Bessie设计了一个游戏:“愤怒的牛奶”。游戏的原型是:有一些可爆燃的草堆分布在一条数轴的不同坐标,玩家用弹弓把一头奶牛发射到数轴上。牛奶砸到草堆上的冲击能量会引发草堆燃爆,并有可能引起附近的草堆连环燃爆。游戏的目标是玩家用一头奶牛燃爆尽可能多的草堆。
有N个草堆在数轴的不同位置,坐标为x1,x2,….,xn。如果玩家把牛发射到坐标是x的草堆上,这个草堆就会燃爆,冲击波的半径是1,距离它是1的草堆也会被燃爆。这些相邻的草堆会同时燃爆,并且冲击波的半径是2。下一步,被燃爆的草堆冲击波半径会是3。一般的,时间t燃爆的草堆,每一个的冲击波半径是t,被这些冲击波引爆的草堆在t+1时刻会产生冲击波半径是t+1,以此类推。
请计算,只用一头奶牛玩家最多可以燃爆多少草堆?输入格式
第一行:一个整数N( 1 ≤ N ≤ 100)。
下面有N行,每行一个整数:x1, x2 ,…,xn,范围在[0…1,000,000,000]输出格式
输出最大可能燃爆的草堆数。
输入样例
6
8
5
6
13
3
4输出样例
5
样例解释
In this example, launching a cow onto the hay bale at position 5 will cause the bales at positions 4 and 6 to explode, each with blast radius 2. These explosions in turn cause the bales at positions 3 and 8 to explode, each with blast radius 3. However, these final explosions are not strong enough to reach the bale at position 13.
#include <iostream>
#include <stdio.h>
#include <algorithm>
using
namespace
std;
int
a[150];
int
n;
int
main()
{
scanf
(
"%d"
,&n);
for
(
int
i=0;i<n;i++)
scanf
(
"%d"
,&a[i]);
sort(a,a+n);
int
ans=1;
for
(
int
i=0;i<n;i++)
{
int
sum=1;//这一次发射会将i也打掉
int
j=i,t=1;//j记录当前扩张到的草堆位置,t表示冲击波当前产生的力量
for
( ; a[j]+t >= a[j+1] && j+1 < n; t++)//当能向右扩张时循环,注意边界
{
int
now=j;
while
(a[now]+t >= a[j+1] && j+1 < n)//如果这一次产生的冲击波打掉的不止一个
{
j++;//算最右边的一个点
sum++;
}
}
j=i-1,t=1;
if
(a[i] - t <= a[i-1] && i != 0)//如果i=0时不需要向左循环
{
sum++;
for
( ; a[j]-t <= a[j-1] && j-1 >= 0; t++)
{
int
now=j;
while
(a[now]-t <= a[j-1] && j-1 >= 0)
{
j--;//算最左边的一个点
sum++;
}
}
}
ans=max(ans,sum);//记录最优值
}
printf
(
"%d"
,ans);
return
0;
}
首先一开始审题不够清楚,以为像第一题一样只能打到某一个草堆上,考虑了很久,重新审了几次题才找到错误,奶牛是可以发射到任意一个坐标上的。然后,这一题是不会出现连环爆炸的,在题目中并没有描述。题目描述
牛奶Bessie设计了一个游戏:“愤怒的牛奶”。游戏的原型是:有一些可爆燃的草堆分布在一条数轴的不同坐标,玩家用弹弓把奶牛发射到数轴上。牛奶砸到数轴上的冲击波会引发附近的草堆燃爆,并有可能引起附近的草堆连环燃爆。游戏的目标是玩家用一些奶牛燃爆所有的草堆。
有N个草堆在数轴的不同位置,坐标为x1,x2,….,xn。如果玩家把奶牛发射到坐标是x,能量是R,就会引爆半径R以内的的草堆,即坐标范围[x-R, x+r]的草堆都会燃爆。
现在有K头奶牛,每头奶牛的能量都是R,请计算如果要引爆所有的草堆,最小的R是多少?输入格式
第一行:2个整数N( 1 ≤ N ≤ 50,000)和K( 1 ≤ K ≤ 10)。
下面有N行,每行一个整数:x1, x2 ,…,xn,范围在[0…1,000,000,000]输出格式
输出最小可能的R。
输入样例
7 2
20
25
18
8
10
3
1输出样例
5
#include <stdio.h>
#include <algorithm>
int
n,k;
int
a[50500];
int
main()
{
scanf
(
"%d%d"
,&n,&k);
for
(
int
i=0;i<n;i++)
scanf
(
"%d"
,&a[i]);
std::sort(a,a+n);
int
l=0,r=100
000 0500;//r初始定大一点,使其最坏情况依然能成立
while
(l < r)
{
int
mid=(l+r)/2;
int
used=0,last=0;//used计算使用的奶牛数,last记录当前冲击波最多炸掉的草堆的编号
while
(last < n)
{
used++;
int
j=last+1;
while
(j < n && a[j] - a[last] <= mid*2) j++;//计算这一次冲击波最多能让哪一个草堆爆炸
last=j;
}
if
(used <= k) r=mid;
else
l=mid+1;
}
printf
(
"%dn"
,l);
return
0;
}
最后
以上就是感性中心最近收集整理的关于USACO Angry Cows总结的全部内容,更多相关USACO内容请搜索靠谱客的其他文章。
发表评论 取消回复