Codeforces Round #335 (Div. 2)

Codeforces Round #335 (Div. 2)
A. Magic Spheres
标题:3色の球で、いずれか2つの同じ色の球を他の色の球に変えることができます.質問、それぞれの色のボールを与えるのは、最後の要求を満たすことができる相応の色のボールの数ですか?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c;
ll x,y,z;
int main()
{
    while(~scanf("%I64d%I64d%I64d",&a,&b,&c))
    {
        scanf("%I64d%I64d%I64d",&x,&y,&z);
        ll ans=0;
        ll sum=0;
        if(a-x>=0)
            ans+=(a-x)/2;
        else
            sum+=x-a;
        if(b-y>=0)
            ans+=(b-y)/2;
        else
            sum+=y-b;
        if(c-z>=0)
            ans+=(c-z)/2;
        else
            sum+=z-c;
        if(ans-sum >=0 )
            printf("Yes
");
        else
            printf("No
");
    }
    return 0;
}

C. Sorting Railway Cars
題意:番号付きcarsの列は、毎回1つの番号の車を一番前または一番後ろに移動することができ、このcarsを昇順に並べ、最小の移動案を求める.
これはもと書いたBCの問題とあまり差がありませんが、それは末尾に置くしかなく、直接t=1を最初からずっと探し続け、n-tを出力すればいいのです.この問題は両側に置くことができるが,そのように書くのは明らかに間違っている.いくつかのサンプルを試してみると、前に置いても後ろに置いてもできるだけ早く昇順に達するためであり、もともと連続昇順であるcarsの中には移動する必要がなく、相対位置自体がバランスしているため、最長連続上昇サブシーケンスの長さを見つけ出すだけでよいことが分かった(ここでの「連続」はa[i]=a[i-1]+1).そしてn^2は通れない(dp方法では書けない、n*lognの方法はループ+二分探索)ですが、ここではO(n)の方法があります.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int a[100010];
int num[100010];
int main()
{
    while(~scanf("%d",&t))
    {
        for(int i=1; i<=t; i++)
        {
            scanf("%d",&a[i]);
            num[a[i]]=i;
        }
        int ans=1;
        int sum=1;
        for(int i=2; i<=t; i++)
        {
            if(num[i]-num[i-1]>0)
                sum++;
            else
            {
                sum=1;

            }
            ans=max(ans,sum);
            //cout <<ans <<endl;
        }
        cout << t-ans <<endl;
    }
    return 0;
}