新龟兔赛跑

新龟兔赛跑

时间: 1ms        内存:64M

描述:

大家还记得龟兔赛跑的故事吗?兔子输给了乌龟,但是他一直都不服气,想要一雪前耻。他把他的族人全部都带来了海边,要与乌龟一族一比高下。嚣张的兔子们,给了乌龟一个月的时间来准备这场世纪大战。如临大敌的乌龟们每天没日没夜的锻炼在高帅富Bearboy的帮助下,乌龟的速度再也不是以前那样了,完全有能力和兔子抗衡。为了比赛的结果更权威,这次兔子提出,要N只兔子和N只乌龟在同一条跑道上同时进行比赛。

嚣张的兔子让乌龟们自己在跑道上选择自己起跑的起点(不一定是跑道的0点),同时让乌龟为这N只兔子规定他们的起点。跑道长度保证所有的超越都可以完成,比赛积分计算如下:

       1x只乌龟同时超过一只兔子   乌龟一族 x

       2x只兔子同时超过一只乌龟   兔子一族 x

       3x只乌龟同时超过y只兔子   乌龟一族 x*y

       4x只兔子同时超过y只乌龟   兔子一族 x*y

问最后谁的分最高。

输入:

输入有多组测试数据。每组测试数据第一行是一个整数N1<=N<=100000),表示兔子和乌龟的数量(都为N)。接下来有2*N行数据,每行有两个数字Si ViSi表示第i只乌龟/兔子的初始位置(跑道起点为0),Vi(1<=Vi<=100000)表示第i只乌龟/兔子的匀速前行的速度)第2行到N+1行是N只兔子的信息,第N+2行到2*N+1行是N只乌龟的信息。(所有的Si互不相等)

输出:

输出乌龟所得的分数(由于结果会很大,所以结果对2012取余数)

示例输入:

3
3 5
7 6
8 2
1 7
2 6
5 8
2
4 2
5 2
3 4
2 4

示例输出:

7
4

提示:

参考答案(内存最优[748]):

#include<stdio.h>
int main()
{
	int n,i,j,sum;
	int a[1000][2],b[1000][2];
	while(scanf("%d",&n)==1)
	{
		sum=0;
		for(i=0;i<n;i++)
			scanf("%d%d",&a[i][0],&a[i][1]);
		for(i=0;i<n;i++)
			scanf("%d%d",&b[i][0],&b[i][1]);
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
				if(b[j][0]<a[i][0]&&b[j][1]>a[i][1])
				{
					sum=sum+1;
					sum=sum%2012;
				}
		}
		printf("%d\n",sum);
	}
				
	return 0;
}

参考答案(时间最优[16]):

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <math.h>
#define Tortoise 1
#define Rabbit   2
using namespace std;
struct type
{
    int s,v,kind;
} Racer[100000];
int n;
bool cmp(type a,type b)
{
    return a.s>b.s;
}
int rabNum[100001];
int lowbit(int x)
{
    return x&(-x);
}
long long int getNum(int x)
{
    long long int sum=0;
    for(; x>0; x-=lowbit(x))
        sum+=rabNum[x];
    return sum;
}
void addVal(int x,int val)
{
    for(; x<=100000; x+=lowbit(x))
        rabNum[x]+=val;
}
int main()
{
    long long int ans;
    while(cin>>n)
    {
        ans=0;
        memset(rabNum,0,sizeof(rabNum));
        for(int i=0; i<n; ++i)
        {
            cin>>Racer[i].s>>Racer[i].v;
            Racer[i].kind=Rabbit;
        }
        for(int i=n; i<(n<<1); ++i)
        {
            cin>>Racer[i].s>>Racer[i].v;
            Racer[i].kind=Tortoise;
        }
        sort(Racer,Racer+(n<<1),cmp);
        for(int i=0; i<(n<<1); ++i)
        {
            if(Racer[i].kind==Rabbit)
                addVal(Racer[i].v,1);
            else if(Racer[i].kind==Tortoise)
                ans=(ans+getNum(Racer[i].v-1))%2012;
        }
        cout<<ans<<endl;
    }
    return 0;
}




题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注