daily 3

CF 1490F

大水题，记录一下每个值出现的次数，然后再记录每个次数出现的次数，之后用map存下来遍历即可

void solve(){
  int n;cin>>n;
  map<int,int,greater<int>>mp1,mp2;
  for(int i=0;i<n;++i){
    int x;cin>>x;
    mp1[x]++;
  }
  for(auto& k:mp1){
    mp2[k.second]++;
  }
  int ans=0x3f3f3f3f;
  for(auto &k1:mp2){
    int i=k1.first;
    int tmp=0;
    for(auto& k2:mp2){
        int j=k2.first;
        if(i==j)continue;
        tmp+=k1.first>k2.first?k2.second*k2.first:(k2.first-k1.first)*k2.second;
    }
    ans=min(ans,tmp);
  }
  cout<<ans<<'\n';
  return;
}

CF 1491C

差分题，首先我们可以知道，对于每一次操作来说，他都会影响之后(i+2,min(n,i+s[i]))区域内的值，那么我们对于区间的修改，就用差分就可以了

需要注意的是一个点最多到1，那么如果修改的值大于了本来的值，那么i+1的点需要替它承受多出来的操作数

void solve(){
  int n;cin>>n;
  vector<int>s(n+1),cnt(n+2),b(n+2);
  for(int i=1;i<=n;++i){
    cin>>s[i];
    int l=i+2,r=min(n,i+s[i]);
    if(l<=r){
        cnt[l]++;cnt[r+1]--;
    }
  }
  for(int i=1;i<=n;++i){
    b[i]=b[i-1]+cnt[i];
  }
  for(int i=1;i<=n;++i){
    if(b[i]>=s[i]){
        b[i+1]+=(b[i]-s[i]+1);//since right now it only effect i+1
    }
  }
  int ans=0;
  for(int i=1;i<=n;++i){
    ans+=max(0ll,s[i]-b[i]-1);
  }
  cout<<ans<<'\n';
  return;
}

CF 1487E

multiset的题目

对于每一种禁忌，存下来，每次我们遍历multiset，然后对每一种物品把其不能共存的值给erase掉，然后再加上begin的值就好了，注意最后判定一下有没有超范围

void solve(){
  vector<int>n(5);
  vector<int>m(5);
  vector<vector<ll>>dish(5,vector<ll>());
  vector E(5,vector<vector<int>>());
  for(int i=1;i<=4;++i){
    cin>>n[i];
  }
  for(int i=1;i<=4;++i){
    dish[i].resize(n[i]+1);
    for(int j=1;j<dish[i].size();++j){
        cin>>dish[i][j];
    }
  }
  for(int i=2;i<=4;++i){
    cin>>m[i];
    E[i].resize(n[i]+1);
    for(int j=0;j<m[i];++j){
        int x,y;cin>>x>>y;
        E[i][y].push_back(x);
    }
  }
  vector<multiset<ll>>st(6);
  for(int i=1;i<=n[1];++i){
    st[2].insert(dish[1][i]);
  }
  for(int i=2;i<=4;++i){
    for(int j=1;j<=n[i];++j){
        for(int v:E[i][j]){
            st[i].erase(st[i].find(dish[i-1][v]));
        }
        if(!st[i].empty()){
            dish[i][j]+=*st[i].begin();
        }
        else{
            dish[i][j]=1e13;
        }
        st[i+1].insert(dish[i][j]);
        for(int v:E[i][j]){
            st[i].insert(dish[i-1][v]);
        }
    }
  }
  if(!st[5].empty()&&*st[5].begin()<1e13){
    cout<<*st[5].begin()<<'\n';
  }
  else{
    cout<<-1<<'\n';
  }
  return;
}

感觉这样刷下去不行，不太在状态，明天还是按专题刷了，先数据结构吧，干脆就从差分刷起，然后每个专题持续三天，酱紫比较好感觉