列表

详情

NC24005. [USACO 2016 Jan B]Angry Cows

描述

Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots a cow with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line; the cow lands on a hay bale with sufficient force to cause the bale to explode, which in turn might set of a chain reaction that causes additional nearby hay bales to explode. The goal is to use a single cow to start a chain reaction that detonates as many hay bales as possible.
There are N hay bales located at distinct integer positions x1,x2,…,xN on the number line. If a cow is launched onto a hay bale at position x, this hay bale explodes with a "blast radius" of 1, meaning that any other hay bales within 1 unit of distance are also engulfed by the explosion. These neighboring bales then themselves explode (all simultaneously), each with a blast radius of 2, so these explosions may engulf additional yet-unexploded bales up to 2 units of distance away. In the next time step, these bales also explode (all simultaneously) with blast radius 3. In general, at time t a set of hay bales will explode, each with blast radius t. Bales engulfed by these explosions will themselves explode at time t+1 with blast radius t+1, and so on.

Please determine the maximum number of hay bales that can explode if a single cow is launched onto the best possible hay bale to start a chain reaction.

输入描述

The first line of input contains N (1≤N≤100). The remaining N lines all contain integers x1…xN (each in the range 0…1,000,000,000).

输出描述

Please output the maximum number of hay bales that a single cow can cause to explode.

示例1

输入: 

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.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 412K, 提交时间: 2020-09-29 22:36:06 

#include<bits/stdc++.h>
using namespace std;
int main(){
   int i,j,k,t,flag,ans=0,s1,s2,n,a[105];
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(i=0;i<n;i++)
    {
        flag=k=1,j=i-1,t=i;
        while(flag)
        {
            flag=0;
            while(j>=0&&a[t]-a[j]<=k)flag=1,j--;
            k++,t=j+1;
        }
        s1=i-t;
        flag=k=1,j=i+1,t=i;
        while(flag)
        {
            flag=0;
            while(j<n&&a[j]-a[t]<=k)flag=1,j++;
            k++,t=j-1;
        }
        s2=t-i;
        ans=max(ans,s1+s2+1);
    }
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 396K, 提交时间: 2020-09-21 08:56:49 

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j,k,t,flag,ans=0,s1,s2,n,a[105];
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(i=0;i<n;i++)
    {
    	flag=k=1,j=i-1,t=i;
		while(flag)
    	{
    		flag=0;
			while(j>=0&&a[t]-a[j]<=k)flag=1,j--;
			k++,t=j+1;
		}
		s1=i-t;
		flag=k=1,j=i+1,t=i;
		while(flag)
    	{
    		flag=0;
			while(j<n&&a[j]-a[t]<=k)flag=1,j++;
			k++,t=j-1;
		}
		s2=t-i;
		ans=max(ans,s1+s2+1);
	}
	printf("%d\n",ans);
    return 0;
}

上一题

© 2024 nowcoder.com