• cf #823 Div.2(A~C)

  ---

  Cf #823 Div.2

  文章目录

  • Cf #823 Div.2
  • • [A. Planets](https://codeforces.com/contest/1730/problem/A)
    • [B. Meeting on the Line](https://codeforces.com/contest/1730/problem/B)
    • [C. Minimum Notation](https://codeforces.com/contest/1730/problem/C)

  A. Planets

  • 题意

    • 有n个星星，第i个颗星星在第a[i]环绕轨道上，用以下两种操作，问最小消耗
    • 操作1:消除单个星星，消耗1。操作2:消除整个轨道的星星，消耗c

  • 题解

    • 对于每一个轨道去考虑消除，x轨道中的星星个数大于c则使用操作2，否则用操作1，保证每一个轨道的消耗最少，贪心正确

  • 代码

  #include 
  #include 
  
  using namespace std;
  
  void solve() {
      int n,c,x; cin>>n>>c;
      map<int,int> h;//h[轨道]->轨道中星星数量
      for(int i=0;i<n;i++) {
          cin>>x;
          h[x]++;
      }
      
      long long ans=0;
      for(auto t:h) {//map的遍历方法
          if(t.second<=c) ans+=t.second;
          else ans+=c;
      }
      
      cout<<ans<<'\n';
  }
  
  int main() {
      int t;
      cin>>t;
      while(t--) solve();
      
      return 0;
  }
  

  B. Meeting on the Line

  • 题意

    • x轴上有n个人，每个人到达某一点的时间为abs(x[i]-x)+t[i]，其中x[i]为第i个人的坐标，t[i]表示第i个人穿衣服所需要的时间。
    • 找到一个位置pos，使得最晚到达pos的人的时间最小

  • 题解

    • 方法一：二分；二分答案时间(最晚到达pos的最小时间)，对于每个时间检验每个人能到达的区间，所有区间有交集意味着答案位置在交集区间中，也就是说答案时间其具有单调性，时间短会使得有人不能到达pos(没有交集区间)，时间越长交集区间会更长，直到二分至交集区间缩在一个长度可视作一个点的区间即找到答案

    • 方法二：贪心；当所有的t[i]=0时，那么容易得到取pos=(x_max+x_min)/2时，使得最晚到达pos的人的时间最小。而将(xi,ti)换成两个点(xi-ti,0)和(xi+ti,0)，易证得最终答案不变，所以只需要将所n个点用以上方法换成2n个点，取最大最小的平均值即为pos

      证明：用(xi-ti,0)和(xi+ti,0)替换(xi,ti)，答案不变
      
      假设答案为pos，pos>xi，那么答案时间为ti+pos-xi
      对于(xi-ti,0),(xi+ti,0)来说其答案时间为pos-(xi-ti)=ti+pos-xi,abs(pos-xi-ti)，其中第一个时间与答案时间相同，第二个时间一定小于答案时间，故不影响答案
      
      对于pos

#include 
#include 

using namespace std;
const int N=1e5+10;

int n;
double x[N],t[N],ans;

bool check(double mid) {//检验答案时间是否能让所有人到达某一个区域
    double l=-2e8,r=2e8;
    for(int i=0;i<n;i++) {
        if(mid<t[i]) return false;//剪枝
        else {
            l=max(l,x[i]-mid+t[i]);
            r=min(r,x[i]+mid-t[i]);
        }//最右的左端点，最左的有端点，贪心找到这样一个区间
    }
    ans=l;//ans也可以取r，因为最终l,r缩在一点
    return r>=l-1e-8;//是否有交集，r
}

void solve() {
    cin>>n;
    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=0;i<n;i++) cin>>t[i];
    
    double l=0,r=2e8;//时间
    while(r-l>1e-7) {//二分实数时间
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.8lf\n",fabs(ans));
}

int main() {
    int t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}

方法二：贪心，O(n)

#include 

using namespace std;
const int N=1e5+10;
double x[N],t[N];

void solve() {
    int n; cin>>n;
    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=0;i<n;i++) cin>>t[i];
    
    double mi=1e9,mx=0;
    for(int i=0;i<n;i++)
        mi=min(l,x[i]-t[i]),
        mx=max(r,x[i]+t[i]);
    printf("%.8lf\n",(mi+mx)/2);
}

int main() {
    int t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}

C. Minimum Notation

• 题意

  • 给定一个只含有0～9的字符串s，可以进行操作：选择第i位将其删除，同时在任意位置插入一个字符x=min(‘9’,s[i]+1)
  • 输出字符串s可以的得到的字典序最小的字符串

• 题解

  • 贪心；当s所有字符单调不递减时，不需要进行任何操作，因为任意一个操作都会使得其中一个字符+1，导致字典序变大。
  • 所以相反的，一旦某个位置递减了，那么该段当中的数都需要进行操作，位置自动放入最佳位置，不需要管。而正向操作记录较为麻烦，所以直接逆序操作，记录一个当前最小的字符x，如果遍历字符大于x，那么操作，s[i]+1数量++，否则不操作，输出的s[i]数量++。因为位置肯定能够保证放在最佳位置，所以最后直接按0～9顺序输出

• 代码

#include 
#include 

using namespace std;

void solve() {
    string s;
    cin>>s;
    int n=s.length();
    
    char x='9';
    int cnt[15]={0};
    for(int i=n-1;i>=0;i--) {//逆序操作
        if(s[i]<=x) {
            x=s[i];
            cnt[s[i]-'0']++;
        }
        else cnt[min(9,s[i]-'0'+1)]++;
    }
    for(int i=0;i<10;i++) cout<<string(cnt[i],'0'+i);
    puts("");
}

int main() {
    int t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}