离散化讲解

大佬讲解离散化

离散化例题

例1

题目链接

例1：Cinema（来自cf）

题目大意

（我说详细点，你就不用翻译了）
n个人，每个人会一种语言；m部电影，每部电影的声音语言和字幕语言都不一样。若某人只能听懂，那么此人将非常满意；若某人只能看懂，那么他将勉强满意。
输入：
输入n，表示人的个数
输入n个数，代表不同语言的序号
输入m，表示电影个数
输入m个数，代表每部电影的声音语言
输入m个数，代表每部电影的字幕语言
输出：
一部电影的序号，此电影让尽可能多的人非常满意，若非常满意的人数相同，那么就再让尽可能多的人勉强满意，若都相同，那么输出任意一个满足条件的即可。

解题思路

大佬给出了板子了，比较好弄了。
直接说一下我的思路吧。
step1：
输入。a，b，c数组分别存人的语言，电影声音语言，电影字幕语言。
step2：
离散化，把a，b，c放在一个数组中，进行去重排序，再为语言重新安排序号。（就是大佬讲解中的板子）
unique函数简单讲解
step3：
遍历每一部电影，对于每一部电影的声音语言和字幕语言，都去人的语言中找有几个，并存在结构体中分开记录，把电影的序号也记下来，因为之后排序后打乱顺序，所以记录下来是必须的。
至于如何找人中符合电影语言的个数，upper-lower就是了。
step4：
对结构体排序，输出。
排序的时候要自定义一个cmp函数，按照输出条件从大到小排序，输出第一个就行。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
const int N=3*M;
struct Movie{
    int very,almost,idx;
}mov[M];
int a[M],b[M],c[M];
int d[N];
bool cmp(Movie a,Movie b){
    if(a.very!=b.very) return a.very>b.very;
    else return a.almost>b.almost;
}
int main(){
    int n,m,num=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=m;i++) cin>>c[i];
    //离散化 
    for(int i=1;i<=n;i++) d[++num]=a[i];
    for(int i=1;i<=m;i++){
        d[++num]=b[i];
        d[++num]=c[i];
    }
    sort(d+1,d+num+1);
    num=unique(d+1,d+num+1)-d-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(d+1,d+num+1,a[i])-d;
    for(int i=1;i<=m;i++){
        b[i]=lower_bound(d+1,d+num+1,b[i])-d;
        c[i]=lower_bound(d+1,d+num+1,c[i])-d;
    }

    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++){
        int cnt1=upper_bound(a+1,a+n+1,b[i])-lower_bound(a+1,a+n+1,b[i]);
        int cnt2=upper_bound(a+1,a+n+1,c[i])-lower_bound(a+1,a+n+1,c[i]);
        mov[i].very=cnt1;
        mov[i].almost=cnt2;
        mov[i].idx=i;
    }

    sort(mov+1,mov+m+1,cmp);
    cout<<mov[1].idx<<endl;
}

例2

题目链接

例2：过河

题目大意

青蛙从0开始蹦，问最少踩到多少石子能过河。
输入L，代表桥长；
输入S，T，M，分别代表最短跳跃距离，最长跳跃距离，石子数目；
输入M个数，表示石子位置。

解题思路

100个石子，1e9的桥，显然要离散化。
比较新颖的是这个不是板子了，这应该如何离散化？
100个石子，1e9的桥，显然很多地方是没有石子的，没有石子的路如果很长，需要好几步才能跳到，跳跃过程中都不会踩到石子或者跨过石子，那我们不妨把他缩小，让青蛙一步到达。因为没踩到或跨越石子的跳跃都是无效的，就比如10的位置有个石子，青蛙从0跳到9的过程，一步跳跃和多步跳过去，对最终结果是没影响的，没经过石子啊。
因此，我们将所有石子间距大于T的石子间距都缩小为T，缩小为T的意义在于，青蛙可以一步跳达或者分两步跨越，本质上包含了未离散化时的状态，跳达与跨越的状态。

离散化实现

sort(pos+1,pos+m+1);
for(int i=1;i<=m;i++)
    dis[i]=pos[i]-pos[i-1];

for(int i=1;i<=m;i++){
    dis[i]=min(t,dis[i]);
    endd+=dis[i];        
    pos[i]=pos[i-1]+dis[i];
    f[pos[i]]=1;
    }

数组介绍：
pos[i]表示第i个石子的位置；
dis[i]表示第i个石子与前一个石子的距离；
f[i]表示i位置是否有石子。
变量介绍：
endd用于保存最终桥长。
过程实现：
step1：因为输入的石子位置不一定是按照从小到大输入的，所有先排一下序。
step2：循环计算相邻石子的间距。
step3：循环，为了更新石子位置；若间距大于了T，间距赋值为T，否则不变；桥长（从0开始的）加上新间距；更新此石子的位置，更新位置是要通过前一个石子的位置加上新间距确定的；同时标记更新完的石子所在位置。

dp实现

不妨把起点0位置看作dp的终点，因为0点是确定的而跳过桥的终点其实是不确定的。
反向dp就行了。
挺像板子的，就是把过程反过来了而已。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N];
int l,s,t,m,endd;
int pos[N],dis[N],f[N];
int main(){

    cin>>l;
    cin>>s>>t>>m;
    for(int i=1;i<=m;i++){
        cin>>pos[i];        
    }

    if(s==t){
        int ans=0;
        for(int i=1;i<=m;i++)
            if(pos[i]%s==0) ans++;
        cout<<ans<<endl;
        return 0;
    }

    sort(pos+1,pos+m+1);
    for(int i=1;i<=m;i++)
        dis[i]=pos[i]-pos[i-1];

    for(int i=1;i<=m;i++){
        dis[i]=min(t,dis[i]);
        endd+=dis[i];        
        pos[i]=pos[i-1]+dis[i];
        f[pos[i]]=1;
    }

    for(int i=endd;i>=0;i--){
        dp[i]=100;
        for(int j=s;j<=t;j++){
            dp[i]=min(dp[i],dp[i+j]+f[i]);
        }
    }

    cout<<dp[0]<<endl;

    return 0;
}

注意

我又没AC，忘了特判特殊情况了！！！
s=t的时候特判一下，要不就只能过80！！！
真ex！！！