acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 题解

    userId_undefined
    喵仔牛奶
    小有名气题解仙人8月全勤卷王9月全勤卷王11月全勤卷王GESP5级
    19阅读
    0回复
    1点赞
  • 题解:运送物资 [GESP六级]

    首先考虑列出每辆车的总行驶路程:s=2*a[i]*p+2*b[i]*(x-p) 根据直觉,a[i]>b[i]的车应当优先分配靠左的p[x],a[i]<b[i]的车应该优先分配靠右的p[x],所以需要排序解决 那怎么排序呢? 在所有a[i]>b[i]的车中,贪心地想,a[i]越多的应该越靠左,但同时也要考虑b[i]的影响,所以应该是a[i]-b[i]越大的越靠左安排;(a[i]<b[i]同理) 证明:排序不等式 适用于代价两两不相关的交换/排序问题 假设对于两辆车i,j,i在p1,j在p2,如果把i移到j更优,就要求原来的总代价大于交换后的总代价,即: 然后贪心模拟即可,注意a[i]=b[i]的情况可以与a[i]>b[i]的情况一同处理变成a[i]>=b[i]

    userId_undefined
    YANLECHENG
    时间刺客时空双修者空间掌握者
    8阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页