weixin_55427638
weixin_55427638
采纳率0%
2021-02-24 10:02

求助源代码,一道原创题!!!!!

【问题描述】 Captain在隧道坍塌前走出了洞穴,他意外的发现了很多金币。有一个数轴,上面的每个点都是整数,上面有N枚金币,第i枚金币所在的位置为x[i](注意可能会有多个金币在同一位置),现在Captain想要拿其中的一些金币,他首先要在数轴上选择一个位置建造存放点,然后要选择一些金币,把他们取走并将其带回存放点,由于金币太重,他一次只能携带一枚金币,并且他在携带一枚金币时,走1单位距离会消耗一点体力,换言之,他将一枚金币带回存放点消耗的体力为金币和货仓之间的距离,而他总共只有T点体力。请问他最多能拿多少枚金币。

【输入描述】第一行输入三个正整数N L T。接下来n行每行输入一个正整数表示x[i]给定数据满足(1<=x[1]<=x[2]<=…<=x[n]<=L)【输出描述】输出一行一个整数表示最多拿到的金币数量。

【样例输入】5 14 6

1 2 10 12 14

【样例输出】3

【样例解释】可以将存放点建在12处,那么拿到10 12 14三个位置的金币总共需要4点体力,所以最多拿到3枚金币。

【数据范围】对于前20%的测试数据N<=100。

对于前40%的测试数据N<=1000

对于另外20%的测试数据L<=2000

对于100%的测试数据N<=100000,L<=10^9,T<=2*10^15

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • weixin_39839147 weixin_39839147 2月前

    这个和背包问题是同一类的问题吧建议看下网上的背包问题解决办法

    点赞 评论 复制链接分享
  • SoftwareTeacher SoftwareTeacher 2月前

    请问你自己能解决多少?  这个社区是讨论技术问题的社区,不是求源码的社区。 

    点赞 评论 复制链接分享