头像

well188




离线:20分钟前


活动打卡代码 AcWing 104. 货仓选址

well188
10小时前

排序的目的是什么?

答:找到中位数a[n/2]的值。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);
    int res=0;
    for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

well188
10小时前
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,t[N];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&t[i]);
    sort(t,t+n);
    LL ans=0;
    for(int i=0;i<n;i++){
        ans+=t[i]*(n-i-1);
    }
    printf("%lld\n",ans);
    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

well188
11小时前

问:额外加个标志位success是干什么的?

答:success这个标志用来判断最后一部分是否能覆盖上,不能省略。下面这段代码只能判断中间是否有缺失部分,但不能判断最后是否有缺失部分:

if (r < st){
    res = -1;
    break;
}

问:r = -2e9 为什么不能挪到for循环外面?

答:这里求的是每次迭代中的最大值,所不是全局最大值。

左端点排序的目的是什么?

答:保证了左端点是不断变大的,也就保证在while循环中,当range[j].l>st后,后面的左端点不会再小于等于st。

思路

acwing907贪心.png

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n;
struct node{
    int l,r;
    bool operator<(const node& b)const{
        return l<b.l;
    }
}range[N];
int main(){
    int st,ed;
    scanf("%d%d",&st,&ed);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&range[i].l,&range[i].r);
    }
    sort(range,range+n);
    int res=0;
    bool success=false;
    for(int i=0;i<n;i++){
        int j=i,r=-2e9;
        while(j<n&&range[j].l<=st){
            r=max(r,range[j].r);
            j++;
        }
        if(r<st){
            res=-1;
            break;
        }
        res++;
        if(r>=ed){
            success=true;
            break;
        }
        st=r;
        i=j-1;
    }
    if(!success) res=-1;
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 906. 区间分组

well188
21小时前

对区间选点的理解

选择左端点:需要与前面的区间进行比较
选择右端点:需要与后面的区间进行比较

思路

步骤1
首先按左端点排序。
步骤二
我们要做的就是枚举每个区间,看看当前区间是不是和现有的组存在交集。
由这种判断方式,我们可以进行如下两种操作:
1、如果当前枚举到的这个区间和某一个组没有交集,我们就把他放入这个组内。【即:当前区间左端点大于现在某个组的右端点,
我们将这个区间归为这一组,注意更新组的右端点】
2、如果当前枚举到的这个区间和现有的所有的组都有交集,我们就不能将这个区间归到组内,而是要给他新开一个组。
【即,当前区间的左端点小于或等于现有的所有组的右端点,我们就从新开一个组】

优化:
在步骤二里面处理当前区间的时候,只有两种操作,可以说是两种选择。一个是与某一个区间没有交集(如1),一个是所有的区间都有交集(如2),但是这两种操作在具体实现的时候,都有一些小小的困难,所以,在这里我们来做一些小小的优化。
我们可以这样做:
如果当前区间的左端点比最小的组的右端点都要小,这不就符合2了么,满足与所有的组都有交集的这个条件。如果不满那就属于1了,因为这个是一个二元问题,不是2就是1

这也就解释了为什么要用小根堆这个东东了,我们只要使用当前所有组的最小右端点就可以了呀!!!

代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n;
struct node{
    int l,r;
    bool operator<(const node& b)const{
        return l<b.l;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
    sort(range,range+n);
    priority_queue<int,vector<int>,greater<int> > h;
    for(int i=0;i<n;i++){
        node t=range[i];
        if(h.empty() || h.top()>=t.l){
            h.push(t.r);
        }
        else{
            h.pop();
            h.push(t.r);
        }
    }
    printf("%d\n",h.size());
    return 0;
}

参考: 链接




well188
1天前

运算符优先即.png

记忆顺序

1、单目运算符
2、双目运算符,先乘除,后加减,再位移。
3、关系运算符,先大于小于,后等于不等于。
4、位运算符,位与,异或在中间,位或
5、逻辑运算符,先与后或
6、三目运算符一个。
7、等于运算符一排
8、逗号运算符收尾。

再简单一点

单目,双目,关系,位运算,逻辑运算,三目等于逗号。




well188
1天前

枚举左端点

枚举左端点后,还要考虑右端点超长覆盖了后面的区间的情况,所以要时时更新ed的值,要选最小的。
acwing908贪心算法.png

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n;
struct node{
    int l,r;
    bool operator<(const node& b)const{
        return l<b.l;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
    sort(range,range+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
        else{
            ed=min(ed,range[i].r); //选择更小的右端点
        }
    }
    printf("%d\n",res);
    return 0;
}

枚举右端点

枚举右端点其实更省力,通过代码可以看出,枚举右端点后,只需考虑下个的左端是否大于 ed 就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n;
struct node{
    int l,r;
    bool operator<(const node& b)const{
        return r<b.r;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
    sort(range,range+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}


分享 贪心算法

well188
1天前

贪心的适用原则

贪心是指每次找局部最优解,就可以找到全局最优解,所以贪心一般要求函数是单峰的。动态规划的限制会少一些,一般是枚举了空间中的所有值,找出了最优解。
这两个算法一般是从经验出发来判断,所以要多做题。
贪心算法的适用.png

当你觉得他是贪心题的时候,千万不要轻易相信题目给的样例。



活动打卡代码 AcWing 905. 区间选点

well188
1天前

贪心的适用原则

贪心是指每次找局部最优解,就可以找到全局最优解,所以贪心一般要求函数是单峰的。动态规划的限制会少一些,一般是枚举了空间中的所有值,找出了最优解。
这两个算法一般是从经验出发来判断,所以要多做题。
贪心算法的适用.png

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n;
struct node{
    int l,r;
    bool operator<(const node& b)const{
        return r<b.r;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
    sort(range,range+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

well188
1天前

哈夫曼树的原理

果子合并.png
果子合并1.png

#include <cstdio>
#include <queue>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int> > q;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int t;
        scanf("%d",&t);
        q.push(t);
    }
    int res=0;  
    while(q.size()>1){
        int a=q.top();q.pop();
        int b=q.top();q.pop();
        res+=a+b;
        q.push(a+b);
    }
    printf("%d\n",res);
    return 0;
}



well188
2天前

解法1–优先队列

思路

如何在朴素做法$n^2$之上进行优化?我们每次都是要取出当前最小的两个数进行合并。由于原序列是有序的,$a[1]$是一定会被取到的。假设我们当前取出的是$a[i]+b[j]$,那么我们下一次取的就是$a[i]+b[j+1]$或$a[i+1]+b[j]$。我们先把$b$序列中所有数与$a[1]$的和放入优先队列,这样就满足了$a[i]+b[j+1]$的情况。(因为$a[1]$一定比$a$数组后面的小)

所以重点就是处理$a[i+1]+b[j]$,每次把取出$b[j]$对应的取到$a$数组中的位置往后移一个加入队列即可。

【注意】优先队列默认是大根堆。所以,要改成小根堆,用 greater

#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int n,a[N],b[N],to[N];
priority_queue<PII,vector<PII>,greater<PII> > q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) {
        scanf("%d",&b[i]);
        q.push((PII){b[i]+a[1],i});
        to[i]=1;
    }
    for(int i=1;i<=n;i++){
        printf("%d ",q.top().first);
        int j=q.top().second;
        q.pop();
        q.push((PII){b[j]+a[++to[j]],j});
    }
    return 0;
}

解法2–数学推断+枚举

思路

当 $i \cdot j > n$ 时,$A_i+B_j$ 一定不是前 n 小的数。

理由:因为两个序列均从小到大排列好了,所以如果 $x<=i$ 而且 $y<=j$ 那么 $A_x+B_y < A_i+B_j $ 。于是至少有 $i \cdot j$ 个数小于等于 $A_i+B_j$ 当 $i\cdot j>n$ 时,一定有多余 n 个数小于等于 $A_i+B_j$ ,所以 $A_i+B_j$ 一定不是前 n 小的数。
于是,我们可以枚举可能成为前 n 小的数的 $A_i+B_j$ ,然后排序输出~~

那么存放和的数组f要开多大?

洛谷1631.png
我写了代码算了一下,$10^5$ 大概有 $1166750$,那么 f 数组就开 $2e6$ 。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10,N2=2e6+10;
int n,cnt;
int d[N],e[N],f[N2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=1;i<=n;i++) scanf("%d",&e[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i*j>n) break;
            f[cnt++]=d[i]+e[j];
        }
    }
    sort(f,f+cnt);
    for(int i=0;i<n;i++){
        printf("%d ",f[i]);
    }
    printf("\n");
    return 0;
}

直接枚举 $i \cdot j <= n$ 的数

上面的做法是枚举所有值,当 $i \cdot j > n$ 就 break,这是比较好想的办法,当然还可以直接枚举所有 $ i \cdot j <= n$ 的数,其实这两种办法时间复杂度差不多,但是这种写法也有独到之处,需要练习一下。人人需要注意 sum 数组要开的足够大才行。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e5+10,N2=2e6;
int n,cnt;
int a[N],b[N],sum[N2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    int len=sqrt(n);
    for(int i=1;i<=len;i++){ //i和j必然有一个小于等于根号n,就枚举这个数
        for(int j=i;j<=n/i;j++){//行,j从i开始,到n/i,保证i*j<=n
            sum[cnt++]=a[j]+b[i];
        }
        for(int j=i+1;j<=n/i;j++){//列,同理,要保证i*j<=n
            sum[cnt++]=a[i]+b[j];
        }
    }
    sort(sum,sum+cnt);
    for(int i=0;i<n;i++){
        printf("%d ",sum[i]);
    }
    printf("\n");

    return 0;
}