[数据结构与算法]Codeforces#740 Div. 2 A |B |C

地址：

传送

A. Simply Strange Sort

题意：
排列数组使它从小到大排列，但是有要求：1）每次只能交换i与i+1项的位置。2）奇数次只能操作奇数项，偶数次只能操作偶数项：且i有范围。

题解：模拟操作即可

代码：

#include <bits/stdc++.h>
using namespace std;
const int mod=10e9+7;
#define ll long long
const int maxn=1e3+3;
int mmax=INT_MIN;
int a[maxn];
int tot=1;
int main()
{
    int t;cin>>t;
while(t--){
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int st=0;
    while(1){
        int flag1=0,flag2=0;
        int flag=0;
        for(int i=1;i<n;i++){
            if(a[i]>a[i+1]){flag=1;break;}
        }
         if(flag==0)break;
         flag=0;
        for(int i=1;i<=n-2;i+=2){
            if(a[i]>a[i+1]){swap(a[i],a[i+1]);}
        }
        for(int i=1;i<n;i++){
            if(a[i]>a[i+1]){flag=1;break;}
        }st++;
         if(flag==0)break;
         flag=0;
        for(int i=2;i<=n-1;i+=2){
            if(a[i]>a[i+1]){swap(a[i],a[i+1]);}
        }
        for(int i=1;i<n;i++){
            if(a[i]>a[i+1]){flag=1;break;}
        }st++;
        if(flag==0)break;
 
    }
    cout<<st<<endl;
 
}
    return 0;
}

B. Charmed by the Game

题意：
a和b打球，交替发球。
发球并失败则可称为破发。
不知道谁先发球。
给出总共回合数，a，b赢球次数，求出可能的破发数。

题解：
设a的发球时赢球数为i，a的发球回合为x，b的发球数为y。
那么a的破发数：（x-i）。
a赢球剩下的次数就是在b发球的时候的赢球。也就是b的破发：（a-i）。
相加就是总破发数。
列举i就行，x和y有两种情况（交换）。
注意：a-i<=y，i也得小于x

代码：

e <iostream>
#include<stdio.h>
#include<set>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=100+10;
int n,m;
int main()
{
    int t;cin>>t;
    while(t--){
        int a,b;cin>>a>>b;
        int x=(a+b)/2;
        int y=a+b-x;
        set<int> ss;
        for(int i=0;i<=a;i++){//a赢的次数,i为发球中赢的次数
            if(i<=x&&(a-i)<=y){
                ss.insert(a-i+x-i);
            }
        }
        swap(x,y);
        for(int i=0;i<=a;i++){
            if(i<=x&&(a-i)<=y){
                ss.insert(a-i+x-i);
            }
        }
        cout<<ss.size()<<endl;
        for(auto it=ss.begin();it!=ss.end();it++)
            cout<<(*it)<<" ";
        cout<<endl;
    }
    return 0;

C. Deep Down Below

题意：
一个英雄，当能力大于怪的能力的时候就可以消灭它并让自己的能力值+1，找出可以闯关的最小能力值。

题解：
多组挑战。能力值越来越大，那就先挑软柿子捏，找所需的最小的。要知道每一组需要最小的值得是本组最大的那个值+1再减去前面怪的个数，找出他们，排序即可。
从最小的开始往大了走，如果可以，就继续走，如果不可以，就补齐差距。注意每次走完一组就加上本组怪的数目。

代码：

e <bits/stdc++.h>
using namespace std;
const int mod=10e9+7;
#define ll long long
const int maxn=1e5+3;
int a[maxn];
int tot=1;
struct point{
   int x;
   int l;
} mmax[maxn];
bool cmp(point x1,point y1){
     return x1.x<y1.x;
}
int f[maxn];
int main()
{
    int t;cin>>t;
while(t--){
    int k;cin>>k;
    for(int i=1;i<=k;i++){
            int n;
            f[i]=1;;
            cin>>n;
            //mmax[0]=n;
            mmax[i].x=INT_MIN;
            mmax[i].l=n;
        for(int j=1;j<=n;j++){
            cin>>a[j];
            if(mmax[i].x<a[j]+1-(j-1)){
                mmax[i].x=a[j]+1-(j-1);
                //f[i]=n-j+1;
            }
            //mmax[i]=max(mmax[i],a[j]+1-(j-1));
        }
 
    }
    sort(mmax+1,mmax+k+1,cmp);
    int ans=0,sum=0;
    for(int i=1;i<=k;i++){
 
        if(mmax[i].x>=sum+ans)ans+=(mmax[i].x-sum-ans);
        sum+=mmax[i].l;
 
    }
   // cout<<"ans:";
     cout<<ans<<endl;
}
    return 0;