CF #679 Div.2 部分

菜菜菜

C. Perform Easily

题意：
有一个吉他，有6个弦，每个弦有一个值$a_i (1\le ai\le10^9)$ ，有无穷大的击弦间隔从$1$开始，设$j$为第$j$个间隔，则击弦位置能发出的音为$a_i+j$，现有$n(1≤n≤100000)$个要发出来的音$b_i(1≤b_i≤10^9)$，求最大的间隔和最小的间隔最小的差值是多少。

题解：

如果我们把$b_i-a_j$存起来，那么我们可以把问题转化为，在这个数组内一个区间，满足这个区间包含所有要发出的声音，那么我们就可以把这些区间的最大的$a_j-b_i$和最小的作查，得到多组，然后求个最小值即可。我们可以先对$a$数组升序排序，然后用一个$set$存$\{b_i-a[6],i\}$，这样得到的数都是最小的，然后每次取最前面的值，删除，然后插入$\{b_i-a[cnt[i]],i\}$，直到$cnt[i]$等于1，这样可以保证和上面的操作是等同的。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define IN insert
#define ER erase
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define endl '\n'


int b[100005],c[600005],cnt[100005];
signed main() {
  FIO;
  int a[6];
  _for(int,i,0,6)cin>>a[i];
  sort(a,a+6);
  int n;cin>>n;
  _for(int,i,0,n)cin>>b[i];
  sort(b,b+n);
  set<pair<int,int>>pa;
  _for(int,i,0,n)pa.IN({b[i]-a[5],i}),cnt[i]=6;
  int ans=INT_MAX;
  while(1){
    int i=(*pa.begin()).SE;
    cnt[i]--;
    if(cnt[i]<0)break;
    pa.ER(pa.begin());
    pa.IN({b[i]-a[cnt[i]],i});
    ans=min(ans,(*pa.rbegin()).FI-(*pa.begin()).FI);
  }
  cout<<ans;
  return 0;
}

D. Shurikens

题意：

现在你有$n$个物品，每个物品的价值是$1,2,3,\dots,n$，现在有$n$个人来买你的东西，买的时候都会买货架上最便宜的，现在给你一个清单，表示的是什么时候摆物品和卖出物品的价值。如果这个清单符合要求，则输出摆放的顺序，否则输出$NO$。

题解：

因为我们在放物品的时候，总是要考虑最后放的物品，则我们可以把这个操作倒过来，定义一个$ans$数组，进行一个单调栈的维护，当我们遇到’-‘的时候如果栈为空，直接压入，否则判断栈顶元素是否大于这个元素，如果大于则压入，否则直接输出”NO”；当我们遇到’+’的时候，如果栈为空，则跳过，否则将栈顶元素存入数组$ans$，最后将$ans$倒序遍历输出即可。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x) x.begin(),x.end()
#define EB emplace_back
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'


signed main() {
  FIO;
  int n;cin>>n;
  vector<int>ans;
  vector<int>op;
  stack<int>st;
  int f=0;
  _for(int,i,0,2*n){
    char x;cin>>x;
    if(x=='+')op.EB(x);
    else{
      int y;cin>>y;
      op.EB(-y);
    }
  }
  reverse(all(op));
  _sfor(it,op){
    if(it=='+'&&!st.empty())ans.EB(st.top()),st.pop();
    else{
      if(st.empty())st.push(-it);
      else if(!st.empty()&&st.top()>-it)st.push(-it);
      else{f=1;break;}
    }
  }
  if(f)cout<<"NO\n";
  else{
    cout<<"YES\n";
    reverse(all(ans));
    _sfor(it,ans)cout<<it<<' ';
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/10/27/CF-679-Div-2-部分/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！