AcWing 第62场周赛
4500. 三个元素
原题链接
思想
pair<int,int> a存储值和对应下标- 对值进行排序，遍历找到三个不同值
- 若存在则输出下标
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
pair<int,int> a[N];
void solve(){
int n;
cin >> n;
for(int i = 0; i < n; i ++){
int x;
cin >> x;
a[i] = {x, i + 1};
}
sort(a,a + n);
int cnt = 0;
int flag = a[0].first;
int ans[10];
ans[cnt] = a[0].second;
for(int i = 1; i < n; i ++){
if(a[i].first != flag){
flag = a[i].first;
ans[++cnt] = a[i].second;
if(cnt == 2) break;
}
}
if(cnt == 2){
for(int i = 0; i <= cnt ; i ++) cout << ans[i] <<" ";
}
else cout << -1 << " " << -1 <<" " << -1;
}
int main(){
solve();
return 0;
}4501. 收集卡牌
原题链接
思想
vector<int> st存储当前可以构成一套的数，当st.size() == n说明可以构成一套vis[i]标记i是否在st中，num存储目前为止的未成套的数及其数量- 若读入的数未在
st中，则将其加入并标记 - 每次加入
st对其进行判断：- 若
st.size() == n说明已成套 - 用
string s标记是否成套，在st.size() == n时进行标记 - 将
st和vis清空，遍历num将未成套的数加入st并标记
- 若
- 输出
s即为答案
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
map<int,int> num;
bool vis[N];
void solve(){
cin >> n >> m;
string s(m,'0');
vector<int> st;
for(int i = 0; i < m; i ++){
int x;
cin >> x;
num[x]++;
if(!vis[x]){
vis[x] = 1;
num[x] --;
st.push_back(x);
if(st.size() == n){
st.clear();
s[i] = '1';
for(int i = 1; i <= n; i ++) vis[i] = 0;
for(auto &j : num){
if(j.second > 0){
j.second --;
st.push_back(j.first);
vis[j.first] = 1;
}
}
}
}
}
cout << s << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}AcWing 4502. 集合操作
原题链接
思想
- max(s)−mean(s)的最大可能值，取决于mean(s)最小z值
- 由题可知序列单调递增
- 则mean(s)一定是从前面获取一段连续的数+该最大值
- 加进来的数和平均值比较
- 如果新加进来的数比平均值小，那么这个当前状态子集元素的平均值一定会减小
- 如果相等，平均值不变
- 如果新加进来的数比平均值大，平均值会增加
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int idx, cnt = 1;
double a[N],s[N];
double check(int u){
return a[idx] - (s[u-1]+a[idx])/u;
}
void solve(){
int _;
cin >> _;
while (_ --){
int op;
cin >> op;
if(op == 1){
cin>>a[++ idx];
s[idx]=s[idx - 1]+a[idx];
}
else{
while(cnt + 1 <= idx && check(cnt + 1) > check(cnt)) ++cnt ;
printf("%.6lf\n", check(cnt));
}
}
}
int main(){
solve();
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-7-30 2，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
