[cf] Codeforces Round #687 (Div 2)

Codeforces Round #687 (Div 2)

A.Prison Break

---

水题，直接找4个角，距离出口最远的距离，就是答案

#include <bits/stdc++.h>
using namespace std;

void file()
{
    #ifdef ONLINE_JUDGE
    #else
        freopen( "d:/workProgram/test.txt","r",stdin );
    #endif
}

int main()
{
    //file();

    int t ;
    cin >> t;
    while(t --){
        int n,m,r,c;
        cin >> n >> m >>r >> c;

        int maxn = 0;
        int a,b;


        ///case1
        a = r - 1;  b = c - 1;
        maxn = max( maxn, a + b);
        ///case2
        a = abs(r - 1); b = abs( c - m );
        maxn = max( maxn, a + b);
        ///case3
        a = abs(r - n); b = abs( c - 1 );
        maxn = max( maxn, a + b);
        ///case4
        a = abs(r - n); b = abs( c - m );
        maxn = max( maxn, a + b);

        cout << maxn <<endl;
    }


    return 0;
}

B.Repainting Street

---

我现在发现cf的题是真的怪，我每次都小心翼翼的做，结果直接暴力枚举就完了，服了
但是这个题的我还是没有想出来

我最开始想用最优的办法来做，就是

1. 找出出现次数最多的数，并以他为指标,如果出现的数相同就以出现最早的那个数为第二个判断指标
2. 扫一遍数组，只要不相同就 i + k - 1(如果没有超过n，后面还有个i++，所以要减个1)
   但是到test4就wa了，我还没来得及看哪里wa了

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int a[maxn];    ///原数组
int cnt[maxn];
vector<int> v;

/// 1.离散化数组
/// 2.找出出现次数最多的数，并以他为指标
///   如果出现的数相同就以出现最早的那个数为第二个判断指标
/// 3.扫一遍数组，只要不相同就 i + k



int Find(int n,int x)
{
    int l = 0, r = n;
    while(l < r)
    {
        int mid = ( l + r ) >> 1;
        if( v[mid] < x ) l = mid + 1;
        else r = mid;
    }

    return r;
}

int main ()
{

    int t;
    cin >> t;
    while(t --)
    {
        memset(a,0,sizeof a);
        v.clear();

        int n,k;
        cin >> n >> k;

        for(int i = 0; i < n ; i ++)
        {
            cin >> a[i];
            v.push_back(a[i]);
        }

        /// 排序 + 去重
        sort(v.begin(),v.end() );
        v.erase( unique(v.begin(),v.end() ) , v.end() );
        for(int i = 0 ; i < n ; i++){
            a[i] = Find( v.size() , a[i] );
        }
        ///test
//        for(int i = 0; i < n ; i++){
//            cout << a[i] << " " << v[a[i]] << endl;
//        }

        ///

        int ans = 0x3f3f3f3f;
        for(int i = 0; i < v.size(); i++){

            int flag = 0;
            for(int j = 0; j < n ; j ++){

                if( v[a[j]] != v[i] ){
                    //cout << a[j] << " " << v[i] << endl;
                    j += k - 1;
                    flag ++;
                }
            }
            ans = min(ans,flag);

        }

        cout << ans << endl;

    }

    return 0;
}