9.25 J组算法总复习

钟语嫣

2026-09-27 10:13:17

发布于：上海

6阅读

0回复

0点赞

1.结构体排序:

当一个对象有多个属性(如学生有姓名,成绩,学号),我们用结构体把它们打包在一起。排序时需要自定义比较规则;告诉sort函数谁在前面

struct stu{
    string name;
    int score;
    int id;
};
bool cmp(stu a,stu b){
    if(a.score!=b.score){
        return a.score>b.score;
    }
}

核心要领:

比较函数时,返回true表示第一个参数排在前面
多关键字排序:当第一个关键字不等时,再比较第二个关键字,以此类推。
用struct定义结构体,把相关数据组织在一起。

识别信号:

"按x排序,若相同则按照y排序"
"输出所有人的排名","第k名","前m名"
稳定排序需要用stable_sort

2.筛法

判断质数和批量求质数是两个不同的问题:

判断质数(试除法):判断单个数n是否是质数,只需要从2到√n遍历查看是否有n的因子即可。
批量求质数(埃氏筛):批量求1-n内所有质数,从2开始,每找到一个质数就把它的所有倍数标记为和数,时间复杂度是O(n log log n)

埃氏筛代码：

bool notP[100005];//notP[i]=1 表示不是质数
int primes[100005],cnt;
//把1~n的质数都存下来
void sieve(int n){
    notP[0]=notP[1]=1;
    for(int i=2;i<=n;i++){
        if(!notP[i]){
            primes[++cnt]=i;
            //标记质数的倍数
            for(int j=2*i;j<=n;j+=i){
                notP[j]=1;
            }
        }
    }
}

3.枚举

枚举三要素:

确定枚举对象:要枚举什么?(枚举答案、枚举子集)
确定枚举范围:循环从哪开始到哪结束?
合法条件:什么样的对象是题目要求的答案?

识别信号:

枚举算法的数据范围通常都不大( $N$ $\le$ 1000)。
"所有方案","有多少种可能","恰好满足"

4.贪心：

贪心算法的核心思想是每一步都做出当前最优的选择，希望局部最优能推导出全局最优。

使用条件:

排序后才能选择。
区间贪心(按开始时间/结束时间/时长排序)

5. 二分查找与二分答案:

二分查找:在有序数组中查找目标值,每次比较中间元素,将搜索范围缩小一半。时间复杂度O(logn)
二分答案:要求解最大值最小或最小值最大,不直接求解,而是二分猜答案,每次check当前猜测是否可行。

//找第一个大于等于x的位置
int l=1,r=n,ans=n+1;
int a[100005]={0};
while(l<=r){
    int mid=(l+r)/2;
    if(a[mid]>x){
        r=mid-1;
    }
    else{
        l=mid+1;
    }
}