本文最后更新于 770 天前,其中的信息可能已经有所发展或是发生改变。
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;
}