Codeforces Round #767 Code Review, 复盘

A. Download More RAM

Tag: greedy sortings
Problem description
My idea(思路): ...

#include <bits/stdc++.h>
using namespace std;

bool sortcol( const vector<int>& v1, 
               const vector<int>& v2 ) { 
 return v1[0] < v2[0]; 
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        int n;
        int k;
        cin >> n >> k;
        vector<vector<int>> a(n);
        for(int j = 0; j < a.size(); j++){
            a[j].resize(2);
        }
        for(int j = 0; j < n; j++){
            cin >> a[j][0];
        }
        for(int j = 0; j < n; j++){
            cin >> a[j][1];
        }
        sort(a.begin(), a.end(), sortcol);
        for(int j =0; j < n; j++){
            if (k >= a[j][0]) k += a[j][1];
            else break;
        }
        cout << k << endl;
    }
}

吃口饭再写...

B. GCD Arrays

Tag: greedy, math, number theory
Problem description
My idea(思路): ...

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        int l, r, k;
        cin >> l >> r >> k;
        if ( l == r && l == 1 ){
            cout << "NO" << endl;
            continue;
        }
        if (l == r && l != 1){
            cout << "YES" << endl;
            continue;
        }
        if ((r-l)%2 == 0){
            if(l % 2 != 0){
                if((r-l)/2 + 1 > k) cout << "NO" << endl;
                else cout << "YES" << endl;
            }else{
                if((r-l)/2 > k) cout << "NO" << endl;
                else cout << "YES" << endl;
            }
        }
        else{
            if((r-l+1)/2 > k) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
    }
}

吃口饭继续写...

C. Meximum Array

Tag: constructive algorithms, greedy, math
Problem description

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using pll = pair<ll,ll>;

int main() {
  ll T;
  cin >> T;
  for(ll cas=1; cas<=T; cas++) {
    ll n;
    cin >> n;
    vector<ll> A(n, 0);
    for(ll i=0; i<n; i++) {
      cin >> A[i];
    }
    vector<deque<ll>> P(n+1, deque<ll>{});
    for(ll i=0; i<n; i++) {
      P[A[i]].push_back(i);
    }

    ll ai = -1;
    vector<ll> B;
    while(ai+1 < n) {
      ll b = 0;
      ll next = ai+1;
      while(!P[b].empty()) {
        next = max(next, P[b].front());
        b++;
      }
      assert(next < n);
      B.push_back(b);
      for(ll i=ai+1; i<=next; i++) {
        assert(P[A[i]].front() == i);
        P[A[i]].pop_front();
      }
      ai = next;
    }
    cout << B.size() << endl;
    for(ll bi=0; bi<B.size(); bi++) {
      cout << B[bi];
      if(bi==B.size()-1) {
        cout << endl;
      } else {
        cout << " ";
      }
    }
  }
}

吃口饭继续写...