题目大意：
刚开始有 p 块钱，商店有 n 件物品，你每次可以只买一件付那一件的钱，也可以买 k 件只付最贵那件的钱，问你最多能买几件 (k<=n<=2e5)

首先我们要明确，如果你买了这一件商品，那么你一定买了比这件商品价格低的所有商品，因为这样买花的钱才会更少，方法才是最优的。

解法一：
这道题用 背包dp 解应该是最直观的，先排序一下，状态要么由前一件转移过来，要么由前 k 件转移过来，即 dp[i] = min(dp[i-1]+a[i],dp[i-k]+a[i])

 

然后我们只要找到买哪一件之前花的钱 <=p 就好了。

 

 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 const int N = 2e5 + 5; 5 int t, n, p, k, ans, a[N], dp[N]; 6 int main() 7 { 8     ios::sync_with_stdio(false); 9     cin >> t;10     while (t--)11     {12         cin >> n >> p >> k;13         for (int i = 1; i <= n; i++)14             cin >> a[i];15         sort(a + 1, a + n + 1);16         ans = 0;17         for (int i = 1; i <= n; i++)18         {19             dp[i] = dp[i - 1] + a[i];20             if (i >= k)21                 dp[i] = min(dp[i], dp[i - k] + a[i]);22             if (dp[i] <= p)23                 ans = max(ans, i);24         }25         cout << ans << '\n';26     }27     return 0;28 }
// 93ms

 

 

解法二：

其实很多人最开始想到的都是贪心，我们不难发现，尽量使用第二个技能永远是最佳的，一旦第二个技能不能再使用，剩下的钱我们就一个一个去买前面价格低的。所以我们只要枚举前 k-1 个单买（ >=k 个的话我们只要用第二个技能买一定更划算）,后面的我们全部用第二个技能买就行了，维护可以买到的数量最大值就好了。

 

 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 const int N = 2e5 + 5; 5 int t, n, p, k, a[N]; 6 int main() 7 { 8     ios::sync_with_stdio(false); 9     cin >> t;10     while (t--)11     {12         cin >> n >> p >> k;13         for (int i = 0; i < n; i++)14             cin >> a[i];15         sort(a, a + n);16         int now = 0, pre = 0, ans = 0, cnt = 0;17         for (int i = 0; i < k; i++)18         {19             now = pre;20             cnt = i;                         // 单买前 cnt 个商品，目前花费 now 元21             if (now > p)22                 break;23             for (int j = i + k - 1; j < n; j += k)        // 第 i 件之后的全部用二技能买24             {25                 now += a[j];26                 if (now <= p)27                     cnt += k;28                 else29                     break;30             }31             ans = max(ans, cnt);32             pre += a[i];33         }34         cout << ans << '\n';35     }36     return 0;37 }
// 108ms