阿威爱买鞋

Diposting di

一、问题概述

题面

阿威家隔壁有一家阿迪屌丝鞋店，鞋店里面有$n$双鞋子在售。第$i$双鞋子的价钱为$a_{i}$元。

阿威想买正好$k$双鞋子。每双鞋子都不能买超过一次。

阿威可以分多次去买鞋子，也就是阿威可以多次去购买鞋子，每次购买都只能买之前没买过的鞋子。

阿迪屌丝店有$m$个特别的优惠活动。第$j$个活动会给你一对$(x_j,y_j)$ ，表示如果在一次购物中正好买了$x_j$双鞋子，那么这次购物中的最便宜的$y_j$双鞋子就会免费。

阿威可以多次(或者不用)利用同一个优惠活动。但是每次购物中只能用一个优惠活动。

虽然阿威很想买鞋，但是阿威最近手头有点紧。阿威想知道买正好$k​$双鞋子最少要花多少钱。阿威最近在谈恋爱(这也解释了阿威为什么手头紧)很忙，所以阿威来拜托你这个单身狗来帮他解决这个问题。

Input

第一行输入包括了三个整数$n$,$m$,和$k$ $(1 \le n, m \le 2 \cdot 10^5, 1 \le k \le min(n, 2000)$ -分别表示鞋店中的鞋子个数，鞋店的优惠活动个数，和阿威需要买的鞋子个数。

第二行输入包括了$n$个整数，表示$a_1, a_2, \dots, a_n$ $(1 \le a_i \le 2 \cdot 10^5)$ 这里的$a_i$表示第$i$双鞋子的价钱。

接下来$m$行输入表示$m$个鞋店的优惠活动。第$j$个优惠活动包括一对整数$(x_i, y_i)$$(1 \le y_i \le x_i \le n)$ 表示如果阿威购买了正好$x_i$双鞋子在一次购物中，那么他在这次购物中的$y_i$双最便宜的鞋子就会免费。

Output

输出一行整数 表示阿威用最理想的购物方式所花费的最少的钱。

Examples

input

1
2
3
4
5
6
7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1

output

1
7

二、算法设计思想

1：首先在不考虑优惠的情况下阿威需要买$k$双鞋子,那么肯定是买最便宜的$k$双鞋子。所以我们就预处理一下对鞋子的价钱排序一下只留下最便宜的$k$双鞋子。 这时候我们就把$n$从可怕的$2e5$变到可爱的$2e3​$了。

2：其次，对于每次活动中的$x_i$可能相同，也就是说可能购买了正好$x_i$双鞋子的优惠力度不一样。那么考虑贪心的我们肯定对于同样的$x_i$肯定是选择优惠力度最大的那就是$y_i​$最大的。所以我们这里再预处理一下对于买同样物品的力度最大优惠。

3：现在我们开始考虑对于每次购物我们可以选择购买一些鞋子,然后再计算购买这些鞋子的价钱减去他们的优惠需要多少钱。

4：那么我们要怎么选择每次购物中我们买的那些鞋子呢？答案是：我们需要买排序后连续的鞋子。

为什么呢，我们最后肯定是需要购买最后的最贵的几双鞋子，那么这最贵的几双鞋子 如果和便宜的鞋子一起购买，那么优惠的就是便宜的鞋子，如果我们这个最贵的鞋子和比较贵的鞋子一起购买那么优惠的就是比较贵的鞋子。这样我们就会节省更多的钱。(较贵的鞋子价钱-便宜的鞋子的价钱)

5：那么我们每次购物选几双鞋子购买呢？答案是：不确定的。

但是可以知道的是每次购物都不会影响下一次购物的选项。所以我们只能枚举每次购物选几双鞋子购买。这里的复杂度是$O(n^2)$ 。那么我们还要就算鞋子的价钱啊。不用担心，还记得我们之前说的已经排好序了嘛？而且我们买次购买的都是连续的k双鞋子，而且每次优惠的也是这连续的k双鞋子中的比较便宜的连续几双。所以我们这里运用前缀和知识。就可以$O(1)$求出每次购物需要的价钱。这里我们可以运用动态规划。 $dp[k]$表示购买了前面$k$个鞋子的最少价钱。

三、测试数据

input

1
2
3
4
5
6
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7

output

1
17

input

1
2
3
5 1 4
2 5 7 4 6
5 4

output

1
17

四、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;

int offer[maxn];
int a[maxn];

ll dp[maxn];
ll sum[maxn];
int n,m,k;

ll dfs(int cnt){
    if(cnt==0)return 0;
    if(dp[cnt]!=-1)return dp[cnt];
    ll ans=1e18;
    for(int i=cnt;i;i--){
        int num=cnt-i+1;
        num=offer[num];
        int r=i+num-1;
        int l=i-1;
        ans=min(ans,dfs(i-1)+sum[cnt]-sum[i-1]-sum[r]+sum[l]);
    }
    return dp[cnt]=ans;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    memset(dp,-1,sizeof(dp));
    sort(a+1,a+1+n);
    for(int i=1;i<=min(2000,n);i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        offer[x]=max(offer[x],y);
    }
    cout<<dfs(k)<<endl;
    return 0;
}

五、总结

这题是一题动态规划加贪心的题目。

首先我们需要分析题目，提取有用的信息，从而把题目简化甚至减少了数据范围。一开始看到$n=2e5$很多算法都无法实施了。但是简化了一下$n=2e3$ 那么就多了一个$O(n^2)​$算法的思路。

其次是对于每一部分的实施的完善。再组合起来从而达到解决整个问题的目的。