• 2024-07-27[题解]P2672 [NOIP2015 普及组] 推销员
    P2672[NOIP2015普及组]推销员为了便于操作,将住户信息按疲劳值从大到小排序。那么对于选\(X\)个住户,有\(2\)种情况:选疲劳值前\(X\)大的住户,答案即为\(\sum\limits_{i=1}^Xa[i]+2\times\max\limits_{i=1}^Xs[i]\)。选疲劳值前\(X-1\)大的住户,然后在剩下的住户中,距离比
  • 2024-06-06CSP历年复赛题-P2672 [NOIP2015 普及组] 推销员
    原题链接:https://www.luogu.com.cn/problem/P2672题意解读:N家住户,每家住户与出入口距离是Si米,推销员每走1米疲劳值+1,向第i家住户推销疲劳值+Ai,推销员推销完原路返回出口,计算在向不同数量X的住户推销时,能达到的最大疲劳值。解题思路:本题是一种贪心选择问题,需要思考出可能的最优