列表

详情


NC206652. 赛车

描述

n 个玩具车,绕着长度为 L 米的环形赛道进行赛车比赛,赛程是绕赛道 m 圈,当赛车完成 m 圈后,赛车将被立刻移出赛道。在比赛中,第 i 辆玩具车将以 的速度匀速运行,玩具车在赛道上运行可以当做质点,多辆玩具车相遇以及超越时,不会相互影响。

为了鼓励玩家前来参赛,主办方推出如下奖励活动:若一辆玩具车 A 在比赛时第1次超越了另一辆玩具车 B ,则 A 车的主人将获得 1 个金币的奖励,若 A 第2次超越了 B ,则会获得 2 个金币的奖励,依次类推,即:A 车第 i 次超越 B 车时,将获得 i 个金币的奖励。注意:只有超越过去才计算,并行不算。

例如:在一次比赛中,有 ABC 三辆车,赛道长为 10米,ABC 的速度分别为 1,2,5(m/s),赛程为 3 圈。比赛过程如下:


所以共需要支出 5 个金币。

在一场比赛中,每辆车的速度 v_i 已知,比赛的主办方想要知道本次比赛需要支出多少个金币。

输入描述

第一行三个整数  以空格隔开,分别表示玩具车的数量,比赛进行的圈数,赛道一圈的长度,其中 
第二行 n 个整数以空格隔开,第 i 个表示 v_i ,表示第 i 辆车的速度,其中

输出描述

输出一个整数,表示需要支出的金币数量的总和。

示例1

输入:

3 3 10
1 2 5

输出:

5

说明:

见题目描述。

原站题解

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

C++11(clang++ 3.9) 解法, 执行用时: 620ms, 内存消耗: 1376K, 提交时间: 2020-05-25 23:54:40

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
const int N=1e5+5;
int n,m,L;
int v[N];
int main()
{
	scanf("%d%d%d",&n,&m,&L);
	for(int i=1;i<=n;i++)
	scanf("%d",v+i);
	std::sort(v+1,v+1+n,std::greater<int>());
	long long ans=0;
	for(int i=1;i<m;i++)
	{
		long long cur=0;
		for(int l=1,r=1;l<=n&&r<=n;l++)
		{
			r=std::max(r,l+1);
			while(r<=n&&1LL*m*v[r]>=1LL*(m-i)*v[l]) r++;
			cur+=n-r+1;
		}
		ans+=cur*i;
	}
	printf("%lld\n",ans);
	return 0;
}

上一题