pta 520 钻石争霸赛 2022 (题目+个人题解)

---------------------------------------------------------------------------------------------------------------------------------

“非诚勿扰”是江苏台一款非常受欢迎的相亲节目，台上的女嘉宾们可以从出场的男嘉宾中选择自己喜欢的牵手离开。问题是怎样才能选到最适合自己的男嘉宾呢？这是个概率问题。

解决这个问题有一种随机算法：假设女嘉宾知道自己最多能在台上录几期节目，也就知道自己最多能见到 N 位男嘉宾，那么她可以选择一个随机数 R（

本题就请你根据男嘉宾的出场顺序，预测一下女嘉宾会牵手哪一位。

输入首先在第一行中给出正整数 N（3≤N≤104），即男嘉宾的数量。第二行给出 N 个互不相同的正整数，第 i 个数字表示第 i 位男嘉宾在女嘉宾心目中的得分。数字均不超过 105，之间以空格分隔。

女嘉宾将以 R=⌊N/e⌋ 为线，采用题面中描述的算法选择牵手的男嘉宾。这里我们取 e=2.718。请在一行中输出她牵手的男嘉宾的序号和真正最适合她的男嘉宾的序号（从 1 开始），数字间以 1 个空格分隔。

如果她一直没有遇到比标准更合适的人，就会独自离开，此时对应的序号输出为 0。

10
23 84 15 29 17 56 85 40 91 28

7 9

10
56 85 17 23 84 15 29 40 31 28

0 2

 ps : 这题看上去还是很简单的,不过本人愣是出了点意外,俩个输出一个对7分,一个对13，对错的测试点刚好想反,当时懵了一下,选了给13分的直接看最后一题去了,现在笑起来要是最后多一个为0判断估计能过

（13分）

#include
using namespace std;
int main()
{
    double e = 2.718;
    int R,N;
    long score[10001];
    cin >> N;
    R = N*1.0/e;
    int max = 1,flag=0;

    for(int z=1;z<=R;z++){
        cin >> score[z];
        if(score[z]>score[max]) max = z;
    }

    bool f = false;
    for(int z=R+1;z<=N;z++){
        cin >> score[z];
        if(score[z]>score[max]){
            flag=z;
            break;
        }
    }
    
//     printf("%d %d",flag,max);
    printf("%d %d",flag,max+flag);
    return 0;
}

--------------------------------------------------------------------------------------------------------------------------------

新式六合彩跟传统六合彩其实没有半点关系，只是姥姥为了出题杜撰出来的一种玩法——每位玩家可以下注一个六位数，如果跟开出来的幸运六位数最接近就可以获奖（所谓最接近，是指该数字与幸运数之差的绝对值最小）。

但规则如果这么简单就没什么可玩的了…… 我们把规则搞复杂一点：首先创建一个有 n×m 个格子的矩阵，保证格子总数不小于玩家总数，可以把所有玩家下注的数字随机放进格子里，每个格子最多放一个。然后我们随机生成一个幸运行号 r （1≤r≤n）和幸运列号 c （1≤c≤m），再随机生成一个幸运六位数。中奖者是第 r 行和第 c 列的所有六位数中与幸运数最接近的那个数字的主人。

本题就请你写个程序实现这个抽奖功能。

输入第一行给出 2 个正整数 n 和 m（1≤n,m≤1000），随后 n 行，每行给出 m 个数字，对应该位置格子里玩家下注的数字。如果这个格子是空的，就用 −1 表示。最后一行给出幸运行号 r、幸运列号 c 和幸运六位数。同行数字间以空格分隔。

注意：行号从上向下递增，列号从左向右递增，均从 1 开始计数。

按照 (行号:列号) 的格式输出中奖者的位置。如果中奖者不唯一，则按照首先在幸运行中从左到右，然后在幸运列中从上到下的顺序输出，每行输出一位中奖者的位置。注意同一个位置只能输出一次。题目保证至少存在一位中奖者。

4 5
233333 000001 -1 888888 666666
001010 369624 777888 -1 999999
480735 100000 591846 369623 123123
456456 591846 000000 501000 233333
2 3 480735

(2:2)
(3:3)

PS ：当时看剩下时间只有20分钟多点,就挑了分高的最后一题写了，这题没看,现在看一下思路还是很清晰的。

思路 ： 数组读入以后对要求的行列开始比较取绝对值最小即可（注意排名并列），结果储存的时候可以俩个数组（或一个vector+数据结构）记录所在位置,如果遇到比当前绝对值小的vector.clear之后继续存就行了

---------------------------------------------------------------------------------------------------------------------------------

7-8 521序列

所谓“521 序列”是指将一个原始整数序列 S 中的每个数字分别乘以 5、2、1 后形成的序列，例如 S= { 5, 2, 1 } 时，其对应的 521 序列就是 { 25, 10, 5, 10, 4, 2, 5, 2, 1 } —— 这里我们不要求这个序列一定具有某种顺序，即 521 序列中元素的顺序是可以打乱的。给定 S 后，计算其对应的 521 序列是很简单的。但给定一个 521 序列，恢复其对应的原始序列 S 就略微复杂一点了。本题就请你恢复任意给定的 521 序列的原始序列。

输入第一行给出正整数 N（<105），为 521 序列的长度。随后一行给出 N 个整数，即给定的 521 序列。所有数字的绝对值不超过 105，以空格分隔。

在一行中按照非递增序输出 521 序列对应的原始序列。数字间以 1 个空格分隔，行首尾不得有多余空格。

题目保证原始序列是存在的。

12
1 -5 10 -1 2 4 5 -2 5 25 10 2

5 2 1 -1

 思路 ： sort 排序（降序写的话）, 接下来排序后的第一个数（n为正）肯定是下一个要输出数的5倍,那么下一个 要找的数就是n/5*2，再下一个是n/5，找到移出集合就行了,负数的话反着来判断。直接O(n)时间复杂度历遍的话最后可能会超时,可以用二分改进历遍,哈哈思路是跟上了,但代码实现还不行(⊙﹏⊙)の呃

（13分比赛时候写的原码）（靠，要是下面那个对0的比较写成大于等于0,除了大数据的测试点应该都能过）

#include
using namespace std;
bool cmp(long x,long y){
    return x >=y ;
}
int main()
{
    vector num;
    vector key;
    long N,a;
    cin >> N;

    for(long z=0;z0){
            long flag = num[0]/5;
            key.push_back(flag);
            long f1=0,f2=0;
            for(long z=1;z=0;z--){
                if(f1==0 && num[z]==flag*2) f1 = z;
                else if(f2==0 && num[z]==flag*1) f2 = z;
                if(f1!=0 && f2!=0) break;
            }
            num.erase(num.begin()+f2);
            num.erase(num.begin()+f1-1);
            num.erase(num.end()-1);
        }

    }

    cout << key[0];
    for(long z=1;z