欢乐赛#31抽象题解（T1,T2）
2024-10-14 22:38:15
发布于：广东
20阅读
0回复
0点赞
T1
首先三个数比较我肯定是不会的
然后聪明的我想到了优先队列
诶🤓👆这不就是可反悔贪心吗
直接上代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
priority_queue <int, vector <int>, greater <int>> q;
int a[4];
int main(){
for(int i = 1; i <= 3; i++){
cin >> a[i];
if(q.size() == 2){
if(q.top() < a[i]) q.pop(), q.push(a[i]);//比他大就放进去
}else q.push(a[i]);//元素没达到两个就直接放
}
int ct = q.top();
q.pop(), ct += q.top();//计算总和
cout << ct;
return 0;
}
T2
题目说白了就是让我们求第 和第 小的数然后相减
第K小的数模板秒了
#include <iostream>
#include <cstdio>
//#include <algorithm>
using namespace std;
int a[200005], b[200005];//由于快排后会变有序降低速度，所以用两个数组
int *partition(int *left, int *right){
int *mid = left + (right - left >> 1);
int *idx;
if(*left < *mid){//我真不会三数比较（
if(*mid < *right) idx = mid;
else{
if(*left < *right) idx = right;
else idx = left;
}
}else{
if(*mid > *right) idx = mid;
else{
if(*left < *right) idx = left;
else idx = right;
}
}
swap(*left, *idx);
int pivot = *left;
while(left != right){//快排
while(left != right && *right >= pivot) right--;
*left = *right;
while(left != right && *left <= pivot) left++;
*right = *left;
}
*left = pivot;
return left;
}
int nth_element(int *left, int *right, int *tmp){
int *idx = partition(left, right);
if(idx == tmp) return *idx;
if(idx < tmp) return nth_element(idx + 1, right, tmp);
return nth_element(left, idx - 1, tmp);
}
int read(){
char c = getchar();
int x = 0;
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}
int main(){
int n = read();
for(int i = 1; i <= n; i++){
a[i] = b[i] = read();
}
cout << nth_element(a + 1, a + n, a + n) - nth_element(b + 1, b + n, b + 1);
return 0;
}
有帮助，赞一个