@[TOC]

Contest100000585 - 《算法笔记》4.7小节——算法初步->其他高效技巧与算法

4.7 其他高效技巧与算法

4.7.1 打表

4.7.2 活用递推

例题：PAT B1040/A10993 有几个PAT
https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616

/*
思想：找到A，则PAT的个数=A左边P的个数 * A右边T的个数；
为了统计P、T的个数，设置变量leftNumP[]数组与rightNumT（不用数组应为记录T时候可以直接计算出PAT个数最终结果），实时更新即可
*/

//4.7.2 活用递推PAT B1040有几个PAT
/*
思想：找到A，则PAT的个数=A左边P的个数 * A右边T的个数；
为了统计P、T的个数，设置变量leftNumP[]数组
与rightNumT（不用数组应为记录T时候可以直接计算出PAT个数最终结果），实时更新即可 
注意乘积的取模 
//  gets(str);PAT不支持gets 
换成  cin.getline(str,MAXN);//读入字符串
*/ 
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; 
const int MAXN = 100010;
const int MOD = 1000000007;
char str[MAXN];//字符串
int leftNumP[MAXN] = {0};//每一位左边（含）P的个数
int main()
{
//  gets(str);PAT不支持gets 
    cin.getline(str,MAXN);//读入字符串
    int len = strlen(str);//字符串长度
    for(int i=0;i<len;i++)//从左到右遍历字符串 
    {
        if(i>0)//如果不是0号位
        {
            leftNumP[i] = leftNumP[i-1];//继承上一位的结果  
        } 
        if(str[i] == 'P')//当前位是P
        {
            leftNumP[i]++;//令leftNumP[i]加1 
        }
    }   
    int ans = 0,rightNumT = 0;//ans为答案，rightNumT记录右边T的个数 
    for(int i=len-1;i>=0;i--)//从右向左遍历字符串
    {
        if(str[i] == 'T')//当前位是T
        {
            rightNumT++;//右边T的个数加1  
        }   
        else if(str[i] == 'A')//当前位是A
        {
            ans = (ans+leftNumP[i] * rightNumT)%MOD;//累积乘积  
        } 
    } 
    printf("%d\n",ans);
    return 0; 
}

4.7.3 随机选择算法

随机选择算法

//4.7.3 随机选择算法  
//从A[left,right]中返回第K大的数
int randSelect(int A[],int left,int right,int K)
{
    if(left == right)   return A[left];//边界
    int p = randPartition(A,left,right);//划分后主元的位置为p
    int M = p - left + 1;//A[p]是A[left,right]中的第M大
    if(K == M)  return A[p];//找到第K大的数
    if(K < M)
    {//第K大的数在主元左侧 
        return randSelect(A,left,p - 1,K);//往主元左侧找第K大 
    } 
    else
    {//第K大的数在主元右侧 
        return randSelect(A,p + 1,right,K - M);//往主元右侧找第K-M大的数 
    }
}

随机选择算法应用

//4.7.3 随机选择算法应用  
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>//用于round 
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int A[maxn],n;//A存放所有整数，n为其个数
//随机选取主元，对区间[left,right]进行划分
int randPartition(int A[],int left,int right)
{
    //生成[left,right]内的随机数 
    int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));
    swap(A[p],A[left]);//交换A[p]和A[left]
    //以下为原先Partition函数划分过程，不需要改变任何东西
    int temp = A[left];//将A[left]存放至临时变量temp
    while(left < right)
    {//此处与temp相比是否需要带等号，
    //<=与>=结果差别不大，此处向下取整，所以用<= 
        while(left < right && A[right] > temp)  right--;//反复左移right 
        A[left] = A[right];//将后面比基准值小的数与基准值互换   
        while(left < right && A[left] <= temp)  left++;//反复右移left   
        A[right] = A[left];//将前面比基准值大的数与基准值互换   
    } 
    A[left] = temp;//把temp放到left与right相遇的地方
    return left;//返回相遇的下标 
} 

//随机选择算法，从A[left,right]中返回第K大的数，并进行切分 
void randSelect(int A[],int left,int right,int K)
{
    if(left == right)   return;//边界
    int p = randPartition(A,left,right);//划分后主元的位置为p
    int M = p - left + 1;//A[p]是A[left,right]中的第M大
    if(K == M)  return;//找到第K大的数
    if(K < M)
    {//第K大的数在主元左侧 
        randSelect(A,left,p - 1,K);//往主元左侧找第K大 
    } 
    else
    {//第K大的数在主元右侧 
        randSelect(A,p + 1,right,K - M);//往主元右侧找第K-M大的数 
    }
} 
 
int main()
{
    srand((unsigned)time(NULL));//初始化随机数种子
    //sum和sum1记录所有整数之和与切分后前n/2个元素之和
    int sum = 0,sum1 = 0;
    scanf("%d",&n);//整数个数
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&A[i]);//输入整数
        sum += A[i];//累计所有整数之和  
    } 
    randSelect(A,0,n-1,n/2);//寻找第n/2大的数，并进行切分
    for(int i=0;i<n/2;i++)
    {
        sum1+=A[i];//累计较小的子集合中元素之和 
    } 
    printf("%d\n",(sum - sum1) - sum1);//求两个子集合的元素和之差 
    return 0;
}

Codeup习题

http://codeup.cn/contest.php?cid=100000587

5067 Problem A 求第k大数

http://codeup.cn/problem.php?cid=100000587&pid=0

//5067 Problem  A   求第k大数
//4.7.3 随机选择算法应用  
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>//用于round 
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int A[maxn],n;//A存放所有整数，n为其个数

//随机选取主元，对区间[left,right]进行划分
int randPartition(int A[],int left,int right)
{
    //生成[left,right]内的随机数 
    int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));
    swap(A[p],A[left]);//交换A[p]和A[left]
    //以下为原先Partition函数划分过程，不需要改变任何东西
    int temp = A[left];//将A[left]存放至临时变量temp
    while(left < right)
    {//此处与temp相比是否需要带等号，
    //<=与>=结果差别不大，此处向下取整，所以用<= 
        while(left < right && A[right] > temp)  right--;//反复左移right 
        A[left] = A[right];//将后面比基准值小的数与基准值互换   
        while(left < right && A[left] <= temp)  left++;//反复右移left   
        A[right] = A[left];//将前面比基准值大的数与基准值互换   
    } 
    A[left] = temp;//把temp放到left与right相遇的地方
    return left;//返回相遇的下标 
} 

int randSelect(int A[],int left,int right,int K)
{
    if(left == right)   return A[left];//边界
    int p = randPartition(A,left,right);//划分后主元的位置为p
    int M = p - left + 1;//A[p]是A[left,right]中的第M大
    if(K == M)  return A[p];//找到第K大的数
    if(K < M)
    {//第K大的数在主元左侧 
        return randSelect(A,left,p - 1,K);//往主元左侧找第K大 
    } 
    else
    {//第K大的数在主元右侧 
        return randSelect(A,p + 1,right,K - M);//往主元右侧找第K-M大的数 
    }
} 
 
 
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        for(int i=0;i<n;i++)
            cin>>A[i];
        //注意此处调用函数时候，K取值，K不为k，题目要求，表示很迷QWQ： 
        //（关于第k大的数：例如序列{1,2,3,4,5,6}中第3大的数是4。） 
        cout<<randSelect(A,0,n-1,n-k+1)<<endl; 
    }
    return 0;
}

总结下：

打表暴力算数组；巧用递推看规律；随机选择算法类似快排
三种方法各有特色