头像

CCabout




离线:1天前


分享 排序

CCabout
1天前
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
//1插入排序
//1.1直接插入排序
void insertSort(int a[],int n){
    int i,j,temp;
    for(int i=1;i<n;i++){
        if(a[i]<a[i-1]){
            temp=a[i];
            for(j=i-1; j>=0&&temp<a[j];j--)
                a[j+1]=a[j];

            a[j+1]=a[j];
        }
    }
} 
//1.2折半插入
void half_insertSort(int a[],int n){
    int i,j,low,high,mid,temp;
    for(i=1;i<n;i++){//从前往后依次选数插入 
        temp=a[i];

        low=0;high=i-1;//每次都是搜索所有a[i]前面的数 
        while(low<=high){//从a[i]前面的数组中,把a[i]锁定在low~high之间,high右边的都比他大,low左边的都比他小 
            mid=(low+high)/2;
            if(temp>a[mid])low=mid+1;
            else high=mid-1;    
        }

        for(j=i-1;j>high;j--)
            a[j+1]=a[j];

        a[high+1]=temp;
    }
} 
//1.3希尔排序 
void shellSort(int a[],int n){
    int temp,i,j,d;
    for(d=n/2;d>=1;d/=2){//步长 
        //接下来在每组内部进行插入排序 
        for(i=d;i<n;i+=d){//
            if(a[i]<a[i-d]){
                temp=a[i];
                for(j=i-d ; temp<a[j]&&j>=0 ; j-=d)//往前找比他小的,放在其后面 
                    a[j+d]=a[j];//后移,让位 

                a[j+d]=temp;//找到了位置,放入 
            }
        }
    }
}

//2交换排序
//2.1冒泡排序
void bubbleSort(int a[],int n){
    int i,j,temp;
    for(int i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(a[j]<a[i]){
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
} 
//2.2快速排序1
int Partition(int a[],int left,int right){
    int temp=a[left];
    while(left<right){
        while(left<right && a[right]>temp)right--;
        a[left]=a[right];
        while(left<right && a[left]<temp)left++;
        a[right]=a[left];
    }
    a[left]=temp;//把temp放到两指针相遇的地方 
    return left;//返回左右指针相遇的地方 
}
void quickSort1(int a[],int left,int right){
    if(left<right){
        int pos=Partition(a,left,right);
        quickSort1(a,left,pos-1);
        quickSort1(a,pos+1,right);
    }
} 
//2.2快速排序2
void quickSort2(int a[],int left,int right){
    if(left>=right)return;

    int i=left-1,j=right+1;
    int temp=a[left];//或者left+right>>1 
    while(i<j){
        do i++;while(a[i]<temp);
        do j--;while(a[j]>temp);

        if(i<j)swap(a[i],a[j]);     
    }
    quickSort2(a,left,j);
    quickSort2(a,j+1,right);
} 

//3选择排序
//3.1简单选择排序
void selectSort(int a[],int n){
    int i,j,min;
    for(i=0;i<n-1;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]);
    }
} 
//3.2堆排序
void HeadAdjust(int a[],int k,int n){//对以k为根的子树进行调整  !其实是up的过程 
    int temp=a[k];//temp暂存子树的根节点

    for(int i=2*k;i<n;i*=2){//有点深度优先遍历的赶脚 !k是父亲,i是儿子 
        if(i<n && a[i]<a[i+1])i++;//取值较大的子节点的下标 
        if(temp>=a[i])break;
        else{//没找到比根大的 
            a[k]=a[i];//将a[i]调整到双亲节点上  !k是根节点的下标 
            k=i;//接下来以i的位置为根的子树继续找 
        }
    } 

    a[k]=temp;

}
void BuildMaxHeap(int a[],int n){
    for(int i=n/2;i>=0;i--){//i从n/2到0,反复调整堆  !最后一个结点是 n/2结点 的孩子 
                            //从小子树到大子树,依次调整!建堆肯定从小到大建哇 
        HeadAdjust(a,i,n);
    }
}
void heapSort(int a[],int n){
    BuildMaxHeap(a,n);
    for(int i=n-1;i>0;i--){//n-1趟交换和建堆过程  !从最后一个结点到根节点的下一个位置 
        swap(a[i],a[0]);//每次堆顶元素都和最后一个元素交换,然后向上调整 
                        //把最小值放到前面!类比简单选择排序  
        HeadAdjust(a,0,i-1);//把剩余i-1个元素整理成堆  !大三角到小三角 
                            //关于i-1:i号此时存的是最大的,已经排好序了,不必参与堆排序的调整 
    }
} 

//4归并排序
void Merge(int a[],int low,int mid,int high){
    int b[100];
    int i,j,k;
    for(i=low;i<=high;i++)b[i]=a[i];
    for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
        b[i]<=b[j] ? a[k]=b[i++]:a[k]=b[j++];
    }

    while(i<=mid)a[k++]=b[i++];
    while(j<=high)a[k++]=b[j++];
}
void mergeSort(int a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
} 

//5基数排序
//通常是链式基数排序 

int main(){
    int a[8]={8,37,56,5,4,35,2,41};
    int n=sizeof(a)/sizeof(a[0]);

    //insertSort(a,n);cout<<"直接插入排序:"<<endl;
    //half_insertSort(a,n);cout<<"折半插入排序:"<<endl;
    //shellSort(a,n);cout<<"希尔排序:"<<endl;

    //bubbleSort(a,n);cout<<"冒泡排序:"<<endl;
    //quickSort1(a,0,n-1);cout<<"快速排序1:"<<endl;
    //quickSort2(a,0,n-1);cout<<"快速排序2:"<<endl;

    //selectSort(a,n);cout<<"简单选择排序:"<<endl;
    //heapSort(a,n);cout<<"堆排序:"<<endl;

    mergeSort(a,0,n-1);cout<<"归并排序:"<<endl;

    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }cout<<endl;

    return 0;
}


分享 胖胖闯关

CCabout
3天前
输入
3
56 67 65
78 45 67
56 55 57
58

输出
yes 292
#include<iostream>
using namespace std;

const int N=100;

int main(){
    int n,b,a[N][N];
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    cin>>b;

    int sum=0;
    int i=0,j=0;
    while(i<n && j<n){
        sum+=a[i][j];
        if(b>=a[i][j])j++;
        else i++;
    }
    if(j==n)cout<<"yes "<<sum<<endl;
    else cout<<"no"<<endl;
    return 0;
}



CCabout
3天前
#include<stdio.h>

int locstr(char *str1,char* str2){
    if(!str1 || !str2)return -1;//先判空

    int i=0,j=0;
    while(*(str1+i) && *(str2+j)){//两个都没到头
        if(*(str1+i)==*(str2+j))++i,++j;//相等,继续后移比较
        else{
            i=i-j+1;j=0;//i回去
        }
    }

    if(*(str2+j)=='\0')return i-j;
    else return -1;
}

int main(){
    char *str1="hedesslloworld";
    char *str2="dess";
    int ans=locstr(str1,str2);
    printf("%d",ans);
    return 0;
}



CCabout
9天前

算法笔记 P134

问题:给出N根木棒长度已知但不一定相等, 现在希望通过切割得到长度相等的K根木棒,求长度相等的K根木棒最长是多少?
如:给3根木棒,长度为10, 24, 15,要切割得到7根长度相等的木棒, 则7根木棒的长度最长为6,其组合为1*6+4*6+2*6。

暴力


#include<cstdio>

const int maxn=10010;

int main(){

    int a[maxn];

    int N, K;

    scanf("%d%d", &N, &K);

    for(int i=0; i<N; i++){

        scanf("%d", &a[i]);

    }

    int num, length=1;

    do{ 

        num=0;

        for(int i=0; i<N; i++){

            num += a[i]/length;//第i根木棒可以切割成长度为length的数目 

            printf("%d ", num);

        }

        printf("\n");

        length++;

    }while(num != K); 

    printf("%d\n", length-1);

    return 0;

}

二分



#include<cstdio>

#include<algorithm>

const int maxn=10010;

int main(){

    int a[maxn];

    int N, K;

    scanf("%d%d", &N, &K);

    for(int i=0; i<N; i++){

        scanf("%d", &a[i]);

    }

    std::sort(a, a+N);

    int left=0, right=a[N-1], mid;

    while(left+1 < right){

        int num=0;

        mid = (left + right) / 2;

        for(int i=0; i<N; i++){

            num += a[i] / mid;

        }

        if(num >= K){

            left = mid;

        }

        else{

            right = mid;

        }

    }



    printf("%d\n", left);

    return 0;

}




CCabout
10天前
题目
2020 年 6 月 8 日,国务院联防联控机制发布《关于加快推进新冠病毒核酸检测的实施意见》,提出对“密切接触者”等八类重点人群“应检尽检”,其他人群“愿检尽检”。
某市设有n个核酸检测点,编号从1到n,其中i号检测点的位置可以表示为一个平面整数坐标(xi, yi)。
为方便预约核酸检测,请根据市民所在位置(X, Y),查询距其最近的三个检测点。
多个检测点距离相同时,编号较小的视为更近。
输入
输入共n+1行。
第一行包含用空格分隔的三个整数n、X和Y,表示检测点总数和市民所在位置。
第二行到第n+1行依次输入n个检测点的坐标。第i+1行(1≤i≤n)包含用空格分隔的两个整数xi和yi,表示i号检测点所在位置。
输出
输出共三行,按距离从近到远,依次输出距离该市民最近的三个检测点编号。
输入样例1
3 2 2
2 2
2 3
2 4
输出样例1
1
2
3
输入样例2
5 0 1
-1 0
0 0
1 0
0 2
-1 2
输出样例2
2
4
1

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000;
int n;
pair<int,int> c[N];
pair<int,int> dist[N];
int main(){
    int x,y;
    cin>>n>>x>>y;
    for(int i=0;i<n;i++){
        cin>>c[i].first>>c[i].second;
        dist[i].first=c[i].first-x+c[i].first-y;
        dist[i].second=i+1;
    }
    sort(dist,dist+n);
    for(int i=0;i<n;i++){
        printf("%d\n",dist[i].second);
    }
    return 0;
}



CCabout
22天前

240.食物链(维护到祖宗节点距离的并查集)

思路

p[i] :i到祖宗节点的距离
       取模3 余数1--可以吃根节点
             余数2--可以被根节点吃
             余数0--与根节点为同类

c++代码

#include<iostream>
using namespace std;

const int N=50010;
int p[N],d[N];

//并查集核心操作
int find(int x){
    if(p[x]!=x){
        int u=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=u;
    }
    return p[x];
}

int main(){

    int n,k;
    cin>>n>>k;

    for(int i=1;i<=n;i++)p[i]=i;

    int count=0;
    while(k--){
        int t,x,y;
        cin>>t>>x>>y;

        if(x>n||y>n)count++;
        else{
            int px=find(x),py=find(y);
            if(t==1){//x和y是同类
                if(px==py && (d[x]-d[y])%3)count++;
                else if(px!=py){
                    p[px]=py;//不妨把py作为根节点

                    d[px]=d[y]-d[x];//x和y是同类,到根节点py的距离应该相等,
                                //即(dx+?-dy)%3==0 所以?=dy-dx,,,?为d[p[x]]
                }
            }
            else{

1. 
                if(px==py && (d[x]-d[y]-1)%3)count++;
                else if(px!=py){
                    p[px]=py;
                    d[px]=d[y]+1-d[x];
                }
            }
        }
    }
    cout<<count<<endl;
    return 0;
}




CCabout
23天前

合并集合 并查集

#include<iostream>
using namespace std;
const int N=100010;

int n,m;
int p[N];

int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main(){
    int a,b;
    char ch;
    cin>>n>>m;

    for(int i=1;i<n;i++)p[i]=i;

    while(m--){
        cin>>ch;
        cin>>a>>b;
        if(ch=='M')p[find(a)]=find(b);
        else if(ch=='Q'){
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}



CCabout
24天前

电话列表(y总代码的搬运工)

#include<iostream>
#include<cstring>
using namespace std;

const int N=100010;
int son[N][10];
bool f[N];
char str[N];

//判断串是否包含其他串作为前缀,不包含返回true(电话本可用)包含其他串作为前缀(电话本不可用)
bool insert(char* str){
    int p=0;
    bool is_match=false;//初始值无前缀串
    bool has_new_node=false;//初始值没有新节点创建

    for(int i=0;str[i];i++){
        int u=str[i]-'0';
        if(son[p][u]==0){son[p][u]=++idx;has_new_node=true;}//有新节点创建
        p=son[p][u];
        if(f[p])is_match=true;//存在以p结尾的串
    }
    f[p]=true;//记录当前串的尾标志

    return !is_match && has_new_node;
    //str遍历过程未遇到串的结束标记--->即没有串作为他的前缀 
    //创建了新节点-->即当前串不是其他串的前缀
    //同时满足以上两条即可用电话列表
}
int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        memset(son,0,sizeof son);
        memset(f,false,sizeof f);

        bool flag=true;
        for(int i=0;i<n;i++){
            cin>>str;
            if(!insert(str))flag=false;//当前输入的串不满足电话列表的条件(有一个不满足flag即为false)
        }
        if(flag)puts("YES");
        else puts("NO");
    }
    return 0;
}