week5

2021-08-12

如题目＞▽＜

Ezzat and Two Subsequences（cf）

链接：

https://codeforces.com/contest/1557/problem/A

思路：

挑大头放前面，剩下的求平均值

int main()
{
    //fast;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin >>n;
        vector<int>a(n);
        for (int i = 0; i < n;i++){
            cin >> a[i];
        }
        sort(a.rbegin(), a.rend());
            double ans = 0;
            for (int i = 1; i < n;i++){
                ans += a[i];
            }
                printf("%.9lf\n", a[0]+ans/(n-1));
    }
    return 0;
}

Moamen and k-subarrays（cf）

链接：

https://codeforces.com/contest/1557/problem/B

思路：

先将原数组排好序，然后依次比较元素组和新数组&a_i&前的数字是否一样，一样的话证明连续递增，可以都划到一个子数组里，不能的话就结束该子数组的划分，总的子数组数目小于等于k就是yes

int main()
{
    fast;
    int t;
    cin>>t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<int>a(n);
        map<int, int> lly;
        for (int i = 0; i < n;i++){
            cin >> a[i];
            lly[a[i]] = i;
        }
        int sub=0;
        sort(a.begin(), a.end());
        for (int i = 1; i < n;i++){
            if(lly[a[i]]==lly[a[i-1]]+1){
                continue;
            }
            sub++;
        }
        sub++;
        //cout << sub << endl;
        if (sub <= k)
        {
            cout << "Yes" << endl;
            }
            else{
            cout << "No" << endl;
        }
    }
    return 0;
}

Reorder Cards（at）

链接：

https://atcoder.jp/contests/abc213/submissions/24883689

思路：

行和列解决思路一样，不妨先考虑列，我们需要移到左面每一列都有数字（右面不用管），不难看出，移动的距离为当前列-当前列之前列中有数字的列，所以结果为，当前列-（移动距离）。我们可以使用去重vector来储存每一位有数字的列，用队列进行按序输入

int main()
{
    fast;
    int h, w, n;
    cin >> h >> w >> n;
    vector<int> X, Y;
    queue<pair<int, int>> q;
    for (int i = 0; i < n;i++){
        int x, y;
        cin >> x >> y;
        q.push(make_pair(x, y));
        X.push_back(x);
        Y.push_back(y);
    }
    set<int> t(X.begin(),X.end());
    X.assign(t.begin(), t.end());
    set<int> t1(Y.begin(),Y.end());
    Y.assign(t1.begin(), t1.end());
    while(!q.empty()){
        int x = q.front().first-(q.front().first-(lower_bound(X.begin(), X.end(), q.front().first) - X.begin()+1));
        int y = q.front().second-(q.front().second-(lower_bound(Y.begin(), Y.end(), q.front().second) - Y.begin()+1));
        cout << x << " " << y << endl;
        q.pop();
    }
        return 0;
}

Reorder Cards（at）

链接：

https://atcoder.jp/contests/abc213/submissions/24883689

思路：

建图，搜索，使用二维数组进行邻接矩阵的建立，按照题意用dfs跑一遍即可

bool vis[MAX];st
int n,step; sc
vector<vector<int>> mp;d
void dfs(int x,int y){
    if(x==n&&y==0&&vis[1]==0){
        cout << 1 << " ";
        return;
    }
    
    cout << x << " ";
    for (int i = 0; i < mp[x].size();i++){
        if(vis[mp[x][i]]==0){
            vis[mp[x][i]] = 1;
            dfs(mp[x][i], 0);
            cout << x << " ";
            vis[mp[x][i]] = 0;
        }
    }
}
int main()
{
    fast;
    cin >> n;
    mp.resize(n+1);
    for (int i = 0; i < n-1;i++){
        int x, y;
        cin >> x >> y;
        mp[x].push_back(y);
        mp[y].push_back(x);
    }
    for (int i = 1; i <= n;i++)
        sort(mp[i].begin(), mp[i].end());
    vis[1] = 1;
    dfs(1, 0);
    return 0;
}

营业额统计（lg）

链接：

https://www.luogu.com.cn/problem/P2234

思路：

我们需要一个能一边插入，一边求大于等于当前数和第一个小于当前数的数据结构，set完美地解决了我们的需求。一定要注意手动插入第一个数以及最大值最小值（防止查找时越界）

int main()
{
    fast;
    int n;
    cin >> n;
    set<int> lly;
    int ans = 0;
    cin >> ans;
    lly.insert(ans);
    lly.insert(-MAX);
    lly.insert(MAX);
    int x;
    for (int i = 1; i < n;i++){
        
        cin >> x;
        Iter a = lly.lower_bound(x);
        if(*a==x)
            continue;
        Iter b = a;
        --a;
        ans += min(abs(*a - x), abs(*b - x));
        lly.insert(x);
    }
    cout << ans ;
    return 0;
}

队列安排（lg）

链接：

https://www.luogu.com.cn/problem/P1160

思路：

既要插入，又要删除，我们便需要链表来进行存储，为了能快速地找到当前数字的对应位置，我们还需要一个迭代器数组存储位置，接下来就是正常的增删了

using Iter = list<int>::iterator;
Iter tmp;
Iter pos[(int)(1e5 + 10)];
//bool erased[maxN];
int main()
{
    int n;
    cin >> n;
    list<int> lis;
    lis.push_front(1);
    pos[1] = lis.begin();
    for (int i = 2; i <= n;i++)
    {
        int k, p;
        cin >> k >> p;
        if(p)
        {
            auto it = next(pos[k]);
            pos[i]=lis.insert(it, i);
        }
        else
        {
            pos[i]=lis.insert(pos[k], i);
        }   
    }
    int m;
    cin >> m;
    for (int i = 0; i < m;i++)
    {
        int t;
        cin >> t;
        if(tmp!=pos[t]){
            lis.erase(pos[t]);
            //pos[t] = tmp;
            pos[t] = tmp;
        }
    }
    for(auto i:lis)
        cout << i << " ";
}