4500. 三个元素

原题链接

Origional Linl

思想

• 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. 收集卡牌

原题链接

Origional Link

思想

• 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. 集合操作

原题链接

Origional Link

思想

• $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;
}