NC206652. 赛车
描述
输入描述
第一行三个整数 以空格隔开,分别表示玩具车的数量,比赛进行的圈数,赛道一圈的长度,其中 ,, 。
第二行 n 个整数以空格隔开,第 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; }