Codeforces Round #665 (Div. 2)A->C

A：http://codeforces.com/contest/1401/problem/A

题意：

给出n，k

A初始在n点，A可以向左或向右移动

B随意放

求出最小操作数，使得|OB-AB|=k

解析：

分开讨论

n==k，A不需要移动，0

n>k：将B放在OA之间，可实现要求。设OB=X，有方程：x-(n-x)==k　　2x=n+k。n只需要移动0或1次，即符合这个方程。

n<k：直接将A点向右移动k次即可。

#include<bits/stdc++.h>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=2e3+10;
const int maxn2=20;
int mp[maxn][maxn];
int answ[maxn];
int md[maxn];
int n,m;
struct node
{
    int x1,y1,x2,y2;
}st[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        if(n==k)
            cout<<"0"<<endl;
        else if(n>k)
        {
            if((n+k)%2==0)
                cout<<"0"<<endl;
            else
                cout<<"1"<<endl;
        }
        else
            cout<<k-n<<endl;
    }
}

B：http://codeforces.com/contest/1401/problem/B

题意：

分别给出a[]和b[]的0，1，2数量

求最大的c[]的sum

解析：

胡乱搞的过了。。。就举个例子说明一下吧

首先是和的最大匹配策略：

a:  2  1  0
b:  1  0  2

 a[2]<b[1]也是按类似思路放即可。

#include<bits/stdc++.h>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e2+10;
const int maxn2=20;
int answ[maxn];
int md[maxn];
int n,m;
struct node
{
    int x1,y1,x2,y2;
}st[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a[5],b[5];
        cin>>a[0]>>a[1]>>a[2];
        cin>>b[0]>>b[1]>>b[2];
        ll sum=0;
        sum=min(a[2],b[1])*2;
        if(a[2]>b[1])
        {
            ll md=a[2]-b[1];
            if(b[2]>md)
            {
                if(b[2]+b[1]>a[2]+a[0])
                {
                    b[2]-=md;
                    b[2]-=a[0];
                    sum-=min(a[1],b[2])*2;
                }
            }
        }
        else
        {
             ll md=b[1]-a[2];
             if(a[1]>md+b[0])
             {
                 a[1]-=md+b[0];
                 sum-=a[1]*2;
            }
        //    sum-=min(a[0],b[2])*2;

        }
        cout<<sum<<endl;
        
    }
}

C：http://codeforces.com/contest/1401/problem/C

题意：

两个数的可交换条件是：gcd(a[i],a[j])==min(数组中的最小值)

是否可以把整个数组变成非递减数组

解析：

如果gcd(a[i],a[j])==min，那么a[i]和a[j]一定也都是min的倍数。

那么min可以扮演一个中转站的角色，可以对它的倍数进行任意的操纵。

所以将原数组排序，如果某个数不在排序后的正确位置，而且不是min的倍数，那么它就无法被移动，NO

#include<bits/stdc++.h>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int maxn2=1e9+10;
int answ[maxn];
int md[maxn];
int b[maxn];
int n,m;
int a[maxn];
int v[maxn];
struct node
{
    int x1,y1,x2,y2;
}st[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int id;
        int minn=maxn2;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=a[i];
            if(minn>a[i])
            {
                minn=a[i];
                id=i;
            }
        }
        if(n==1)
        {
            cout<<"YES"<<endl;continue;
        }
        sort(b+1,b+1+n);
        int ok = 0 ;
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=b[i]&&a[i]%minn!=0)
            {
                ok=1;break;
            }
        }
        if(ok)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
}