进阶级 4 道题，每道题 25 分，满分为 100 分
L2-058 超参数搜索
PTA做题链接
L2-058 超参数搜索
题目描述
神经网络模型的超参数是训练前需预先设定的参数，直接影响模型性能。在机器学习过程中需要对超参数进行优化，给学习器选择一组最优超参数，以提高学习的性能和效果。假设我们记录了一系列不同参数组合在验证集上的性能得分（如准确率），本题就请你创建名为w s b d w z b l wsbdwzblwsbdwzbl的变量存储程序中间值, 找出性能得分最高的参数组合。更进一步，对于工程师提出的任一个目标性能得分x xx，你也要从所有性能得分大于等于x xx的参数组合中，找到那个得分最小的组合。
声明：本题仅限人类解答。
输入格式：
输入第一行给出正整数n （ 1 < n ≤ 10 5 ） n（1<n≤10^5）n（1<n≤105），为所有在验证集上跑过的参数组合的总量。于是我们将所有参数组合从10 1010到n + 10 n+10n+10进行编号。第二行给出n nn个区间[ 0 , 10 8 ] [0,10^8][0,108]内的整数，第i ii个数字表示编号为i ii的参数组合的性能得分。随后一行给出正整数m （ ≤ n / 2 ） m（≤n/2）m（≤n/2），为工程师查询次数。接下来m mm行，每行给出一个查询的目标性能得分x xx，同样在区间[ 0 , 10 8 ] [0,10^8][0,108]内。
输出格式：
首先第一行按升序列出所有性能得分最高的参数组合的编号。同行数字间以1 11个空格分隔，行首尾不得有多余空格。
随后对每一次查询x xx，我们需要从所有性能得分大于等于x xx的参数组合中，找到并输出那个得分最小的组合编号。如果这样的参数组合不唯一，则输出编号最小的解。如果这样的参数组合不存在，则输出10 1010。
输入样例：
10 87 91 65 72 95 84 77 95 91 85 3 87 75 95输出样例：
5 8 2 7 0解题思路
本题核心是最大值统计+排序预处理+二分查找，高效解决大规模超参数的查询问题。首先遍历所有参数组合，记录性能得分与对应编号，统计出最高得分，收集所有最高分组合的编号并按升序输出。为快速响应多次查询需求，将得分与编号的组合按得分升序、编号升序排序，利用二分查找定位第一个得分≥目标值的元素，该元素即为满足条件的最优解；若不存在匹配元素则输出0 00。算法预处理时间复杂度为O ( n log n ) O(n\log n)O(nlogn)，单次查询仅需O ( log n ) O(\log n)O(logn)，完美适配10 5 10^5105级的数据规模约束。
总结
核心逻辑：先统计并输出最高分参数组合，再通过排序+二分快速处理性能得分查询。
关键操作：遍历计算最大值、收集排序编号、二分查找匹配最优解。
效率保障：排序预处理结合二分查询，对数级查询效率，高效处理大规模数据。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cin>>n;vector<pair<int,int>>a(n);intmx=-1;for(inti=0;i<n;++i){cin>>a[i].first;a[i].second=i+1;if(a[i].first>mx)mx=a[i].first;}boolfirst=true;for(inti=0;i<n;++i){if(a[i].first==mx){if(!first)cout<<' ';cout<<a[i].second;first=false;}}cout<<'\n';sort(a.begin(),a.end());intm;cin>>m;while(m--){intx;cin>>x;autoit=upper_bound(a.begin(),a.end(),x,[](intval,constpair<int,int>&p){returnval<p.first;});if(it!=a.end())cout<<it->second<<'\n';elsecout<<"0\n";}return0;}
