Luogu 1248 加工生产调度

题目

题目链接: https://www.luogu.org/problemnew/show/P1248

这道题目暴力显然不可取$ 1000!$ , DP 的状态不太容易定义,只能贪心大法

分析贪心

我们可以先假设只有两个物品$ A $ 和$ B $,则存在以下两种情况($ x $代表物品在 A 工厂加工所需时间,$ y $ 代表 B 工厂,以下同理)

  1. 先加工$ A $后加工$ B $,则时间为$ A.x + B.y + \max(A.y, B.x) $
  2. 先加工$ B $后加工$ A $,则时间为$ A.y + B.x + \max(A.x, B.y) $

则若先加工 A 比先加工 B 优,应满足
$$
A.x + B.y + \max(A.y, B.x) < A.y + B.x + \max(A.x, B.y) \\
\begin{align}
&= \max(A.y, B.x) – A.y – B.x < \max(A.x, B.y) – A.y – B.x \\
&= -\min(A.y, B.x) < -\min(A.x, B.y) \\
&= \min(A.x, B.y) < \min(A.y, B.x)
\end{align}
$$
然后放到cmp里,A 了?

等一下,这个方法……是错误的

继续阅读“Luogu 1248 加工生产调度”

排序算法 — O(d(r+n)) — 基数排序

写在前面


基数排序Redix Sort,是为数不多不是基于比较的排序,至今此类我们学过的,也就只有基数排序和桶排不基于比较,桶排的效率自然快,但是对内存的消耗不容小视,基数排序则在空间和时间都有这不错的表现,在大多数情况基本于归并排序速度相近,如果你会一些高端的优化的话,他甚至能够吊打桶排

基数排序

时间复杂度: O( d ( r + n ) )
空间复杂度: O( rd + n )
相信你已经根据前文知道,基数排序,不是基于比较的排序,哪们我们如何排序呢? 我们知道桶排的思想是确定其有或没有,然后遍历 但是我们能不能简化?简化成将每一位桶排? 当然可以,这就是基数排序 我们在每一位上进行桶排,让后进行下一位,直到最所有数高位 听起来貌似是很简单的问题,不过现在有一个重要的问题,怎么分离位?

十进制分离法


我们的数字是十进制,而且十进制分离位在C++中依旧很方便 代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[10][110000];
int redix[10][110000];
inline int ws(int t,int n){
    t--;
    while(t--){
        n/=10;
    }
    return n%10;
}
// ws 分离位数
bool x;// 判断最高位
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tmp=ws(1,a[i]);
        last_redix[tmp][++last_cnt[tmp]]=a[i];// 完成第一位的桶
    }
    for(int t=2;;t++){
        x=false;
        for(int i=0;i<=9;i++){
            for(int j=1;j<=last_cnt[i];j++){// 按照上一位的顺序,不然排序顺序会乱
                tmp=ws(t,last_redix[i][j]);
                if(tmp!=0) x=true;
                redix[tmp][++cnt[tmp]]=last_redix[i][j];// 桶排
                //j++;
            }
        }
        if(!x) break;
        memcpy(last_redix,redix,sizeof(redix));// 复制当前到上一次
        memcpy(last_cnt,cnt,sizeof(cnt));
        memset(cnt,0,sizeof(cnt));
    }
    for(int i=0;i<=9;i++)// 输出
        for(int j=1;j<=last_cnt[i];j++)
            printf("%d ",last_redix[i][j]);
}

二进制分割法


但是显然这种位数分离法比较耗时,要是我们能够快一点…… 等一下,二进制时直接位运算就可分离二进制位了啊 代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[2][1100];
int redix[2][1100];
inline int ws(int t,int n){
    t--;
    while(t--){
        n/=10;
    }
    return n%10;
}
bool x;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        //tmp=ws(1,a[i]);
        last_redix[(a[i])&1][++last_cnt[(a[i])&1]]=a[i];
    }
    for(int t=1;t<=31;t++){
        //x=false;
        for(int i=0;i<=1;i++){
            for(int j=1;j<=last_cnt[i];j++){
                //tmp=ws(t,last_redix[i][j]);
                //if(tmp!=0) x=true;
                redix[(last_redix[i][j]>>t)&1][++cnt[(last_redix[i][j]>>t)&1]]=last_redix[i][j];
                //j++;
            }
        }
        //if(!x) break;
        memcpy(last_redix,redix,sizeof(redix));
        memcpy(last_cnt,cnt,sizeof(cnt));
        memset(cnt,0,sizeof(cnt));
    }
    for(int i=0;i<=1;i++)
        for(int j=1;j<=last_cnt[i];j++)
            printf("%d ",last_redix[i][j]);
}
原理和上面一样,分离位数请参考下一篇: 位运算

End

]]>

NOIP 2011 普及组 第三题 瑞士轮

认真读题很重要

简单分析


题目链接:[https://www.luogu.org/problemnew/show/P1309]
很容易发现,这道题目考察的排序,排序我们第一个肯定想到的是sort或者是归并排序,的确时间复杂度分别是O(n log2(n) )O(n log(n) )可如果是多次计算呢? 排除快排是因为不稳定性 所以总时间复杂度约为: sort O( r*2n^2*log2(2n) ) 归并 O( r*2n^2*log(2n) ) 看看数据范围emmmm 据说这样会 60 分,剩下的你懂的 所以我们需要优化 很显然sort已经没有优化的余地了,所以我们要从归并考虑 然后我们发现每次增减分的数组是单调的 也就是说我们只需要在开始的时候全部排序,后面我们每次只需要花O(n)的时间合并即可 这样子的时间复杂度约为:O( r*n^2 ) 稳如老狗啊!!!

代码


#include <cstdio>
#include <algorithm>
using namespace std;
int n,r,q;
struct node {
    int n,s,p;// n 号码 s 分数 p 能力
}a[210000],left[110000],right[110000];
int lcnt,rcnt,cnt,result_start;
// cmp 不解释
bool cmp(node a,node b){
    if(a.s==b.s) return a.n<b.n;
    else return a.s>b.s;
}
// 合并区间,参照归并排序
void marge(int left_start,int right_start){
    result_start=1;
    while(left_start<=n&&right_start<=n){
        if(cmp(left[left_start],right[right_start])) a[result_start++]=left[left_start++];
        else a[result_start++]=right[right_start++];
    }
    while(left_start<=n) a[result_start++]=left[left_start++];
    while(right_start<=n) a[result_start++]=right[right_start++];
}
int main(){
// 读入
    scanf("%d%d%d",&n,&r,&q);
    for(int i=1;i<=2*n;i++){scanf("%d",&a[i].s);a[i].n=i;}
    for(int i=1;i<=2*n;i++) scanf("%d",&a[i].p);
    sort(a+1,a+1+2*n,cmp);
    for(int i=1;i<=r;i++){
        lcnt=rcnt=0;// 模拟比赛过程
        for(int j=1;j<=2*n;j+=2){
            if(a[j].p>=a[j+1].p){
                a[j].s+=1;
                //printf("%d\n",++cnt);
                left[++lcnt]=a[j];right[++rcnt]=a[j+1];
            }
            else{
                a[j+1].s+=1;
                //printf("%d\n",++cnt);
                right[++rcnt]=a[j];left[++lcnt]=a[j+1];
            }
        }// 排序不解释
        if(i==1) sort(a+1,a+1+2*n,cmp);
        else marge(1,1);
    }
    printf("%d",a[q].n);
}

End


灵活运用每一种算法是一个非常重要的艺术 ]]>

排序算法(3) — O(n log(n)) — 快速排序/归并排序

写在前面 这次是两种大家十分熟悉也是常见的东西,在中间的代码力玩花样的题并非没有,总而言之这是两种十分神奇的算法了qwq

归并排序

时间复杂度: O(n log(n)) 空间复杂度: O(n) 突然间想起几篇前的O(n^2)….真是感人 然后再看看前面的代码长度,在看看下面的… 也是很感人呢2333 我还不如等量子计算机出来直接冒泡
#include <cstdio>
using namespace std;
int n;
int result[110000];
int a[110000];
void marge(int *data,int start,int end,int *result){// 合并区间
    int left_start,result_start,right_start;
    left_start=result_start=start;
    right_start=(start+end+1)/2+1;
    while(left_start<=(start+end+1)/2&&right_start<=end){
        if(data[left_start]<data[right_start]) result[result_start++]=data[left_start++];
        else result[result_start++]=data[right_start++];
    }
    while(left_start<=(start+end+1)/2) result[result_start++]=data[left_start++];
    while(right_start<=end) result[result_start++]=data[right_start++];
}
void margesort(int *data,int start,int end,int *result){// 二分
    if(end-start==1){// 刚好差为1,那么这两个相邻,就可以排序
        if(data[start]>data[end]){
            int temp=data[end];
            data[end]=data[start];
            data[start]=temp;
        }
        return ;
    }
    else if(end-start==0) return ;//相同你排个瓜皮啊
    else {
        margesort(data,start,(start+end+1)/2,result);//继续二分排序
        margesort(data,(start+end+1)/2+1,end,result);
        marge(data,start,end,result);// 合并
        for(int i=start;i<=end;i++) data[i]=result[i];//排序完的总的回去吧233
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    margesort(a,1,n,result);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
我给你讲这个代码还是压过行的 上面的注释我觉得知道原理估计看不懂,说一下归并排序的原理:
  1. 将一个长度为n的数列分成2/n的数列<分>
  2. 分到只剩两个的时候排序<治>
  3. 将每个区间进行合并<和>
所以这是一个分治算法,“分而治之”,“分完要和”。 建议思考两个问题 并不会公布答案,因为不自己想的话根本理解不了 如果你是dalao建议你左上角,这是一篇对你没有用的文章:
  • 在二分排序的时候(start+end+1)/2(start+end+1)/2+1是为了什么,可不可以替换?
  • 中间几个<=是否可以换成<

快速排序

理论最优速度: O(n log(n)) 最差速度: O(n^2) 空间复杂度: O(n log(n)) 我们找出一个“哨兵”,然后找出比他大的和比他小的,然后分成两列<分>,知道最后只剩两个完成排序<治>,然后回溯输出<合> 又是一个分治算法 代码:
#include <cstdio>
using namespace std;
int n;
int a[110000];
void qsort(int *data,int s,int e){
    int o_l=s,o_r=e;
    int base=data[(s+e)/2];//取中快排
    do{
        while(data[s]<base) s++;// 比自己大的
        while(data[e]>base) e--;//比自己小的
        if(s<=e){//上面两个循环都被打断说明顺序不对,交换一下
            int temp=data[s];
            data[s]=data[e];
            data[e]=temp;
            s++;
            e--;
        }
    }while(s<=e);
    if(o_l<e) qsort(data,o_l,e);//确保不越界
    if(s<o_r) qsort(data,s,o_r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    qsort(a,1,n);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

End

这两种算法是比较常见的排序算法,原理都是分治,不过归并相对稳定一些,不容易翻车 ]]>

排序算法(2) — 非常规排序 — sort/桶排

写在前面 为什么说这两个是非常规排序,第一个是stl库,第二个是真的暴力出奇迹233

sort

理论最优时间复杂度: O(n log2(n)) 因为这个东西忘记了所有排序的人估计不止我一个
sort(start,end,cmp);
此函数位于algorithm库中
  • start 开始排序的位置<必选项>
  • end 结束排序的位置<必选项>
  • cmp() 排序的优先级实际上如果要用优先队列你还会见到他<可选项,不填写的话就是升序排列啦>

示例


这个东西真的是超级好用的,吹暴sort!!! 数组排序<升序>:
sort(a,a+n)// 从a[0]到a[n-1]
数组排序<降序>:
bool cmp(int c,int d){
    return c>d;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) printf("%d",a[i]);
}
相比你们也已经猜到了结构体排序的方法:
bool cmp(node c,node d){
    if(c.a>d.a) return true;
    else if(c.b>d.b) return true;
    else return false;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&a[i].a,&a[i].b);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) printf("%d %d\n",a[i].a,a[i].b);
}
所以说这玩意这么好为什么还要用别的呢对吧 如果你想验证一下自己是否学会sort可以试试这道题:[https://www.luogu.org/problemnew/show/P1093]

桶排

时间复杂度:O(max)(max是指数列中间的最大值) 空间复杂度:常数级别 不知道大伙还记不记得在bfs时我们所打的哈希表,桶排与这个东西神似 不知道也没关系 我们想一下,我们打一张表,出现过得数字为true,没有出现过的为false,然后从头遍历,这真的一点都不常规排序…… 伪代码:
    for(int i=1;i<=n;i++){
        scanf("%d",&temp);
        if(temp>max) max=temp;
        x[temp]++;
    }
    for(int i=1;i<=max;i++) {
        for(int j=1;j<=x[i];j++){
            printf("%d ",i);
        }
    }
皮到一个境界2333

End

总而言之,这篇讲的两个不常规排序并不需要理解方法,并且时间复杂度真的是一低再低了233,可谓是简单粗暴还省时,不过缺陷也是有的啦,sort速度终究还是快不过归并,桶排的内存就很感人了… ]]>

排序算法(1) — O(n^2)类型 — 冒泡排序/插入排序/选择排序

写在开头

为什么会有这个系列的文章


因为博主发现自己对排序算法似乎一无所知…所以打算来一发补习

其他


实际上关于对数据的排序一直是一个非常大的问题,我们会发现当数据规模小的时候,多重循环比挨个对并不是什么问题的说,但是在我们的生活当中,我们会发现,数据量讲绝对不止1000这道卡,所以我们必须要在中间找到更多更快更好的算法,至于我为什么没有去讲一些奇怪的排序方法(比如猴子排序)是因为它们是一些人们突发奇想的东西,我们虽然不能说它们坏,不过在实际生活中,用处 可能 并不大,所以我们就不会再去提及它们了,有兴趣的话,自己查查吧. 不要去百度!不要去百度!

冒泡排序

时间复杂度: O(n^2) 空间复杂度: 常数级反正就是你只需要存下来就没啥事了 伪代码:
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(a[i]>a[j]){
            int temp=a[j];
            a[j]=a[i];
            a[i]=temp;
      }
    }
}
很明显我们可以看得出来,所谓冒泡排序,就是两个两个之间互相比对,然后大的往上交换(冒泡),于是打了最后,就完成了排序。 所以时间也就意料之中的高2333

插入排序


时空复杂度: 同上 伪代码:
for (int i=1;i<=n;i++){
    if (a[i-1]>a[i]){
        int temp=a[i];
        int j=i;
        while(j>0&&a[j-1]>temp){
            a[j]=a[j-1];
            j--;
        }
        a[j]=temp;
    }
}
为什么我感觉比上面的那种还暴力 暴力出奇迹233 这种办法的本质就是直接插入,找到比自己大的很比自己小的,然后往中间插队(插入),然后出来就算排序好了 巧了入学时队伍就是这么排出来的的

选择排序

时空复杂度:仍然同上
for(i=1;i<=n;i++){
    min=i;
    for(j=i+1;j<=n;j++){
        if(a[j]<a[min])
            min=j;
    }
    if(min!=i) swap(a[i],a[min]);
}
真是越来越暴力了 然而我们会有很多的排序算法会从这里优化而来,所以说多少还是要学的,起码要知道概念的说不然初赛考到,博主就凉了 这一种排序算法是找到最大和最小然后交换 突然想起初一上时学有理数是疯狂对绝对值排序

End


O(n^2)的算法基本上到此为止,后面的排序算法有很多都是从此衍生的,所以说暴力出奇迹是真的2333 ]]>