Codeforces Round #424 题解

A. Unimodal Array

水题，关键要看清楚题意。

#include <bits/stdc++.h>
using namespace std;
int n, a[110];

int main()
{
    while(~scanf("%d",&n)){
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        int t = 2;
        while(a[t]>a[t-1]) t++;
        while(a[t]==a[t-1]) t++;
        while(a[t]<a[t-1]) t++;
        if(t<=n) puts("NO");
        else puts("YES");
    }
    return 0;
}

B. Keyboard Layouts

水题，用map映射一下就可以了。

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

map<char,char>mp;
string s1,s2,s3;
int main(){
    cin>>s1>>s2>>s3;
    for(int i=0; i<26; i++){
        mp[s1[i]]=s2[i];
        mp[char(s1[i]-32)]=char(s2[i]-32);
    }
    for(int i=0; i<s3.size(); i++){
        if(isdigit(s3[i])) printf("%c", s3[i]);
        else printf("%c", mp[s3[i]]);
    }
    printf("\n");
}

C. Jury Marks

题意：给你n个评委打分的情况，和其中k次分数，问你初始分数的可能数。
解法：首先出力出打分的前缀和，能知道到第i个人评分后距离初试分数的差值然后排序，去重。之后再统计次数，如果次数等于n说明这个分数就可以。

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

unordered_map<int,int>mp;
int a[2010], b[2010] , sum[2010];
vector <int> v[2010];
int main()
{
    int k, n, ans;
    while(~scanf("%d%d",&k,&n)){
        mp.clear();
        memset(sum, 0, sizeof(sum));
        ans = 0;
        for(int i=1; i<=k; i++){
            scanf("%d", &a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        for(int i=1; i<=n; i++){
            scanf("%d", &b[i]);
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=k; j++){
                int t = b[i] - sum[j];
                v[i].push_back(t);
            }
            sort(v[i].begin(),v[i].end());
            v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
        }
        for(int i=1; i<=n; i++){
            for(int j=0; j<v[i].size(); j++){
                mp[v[i][j]]++;
            }
        }
        for(unordered_map<int,int>::iterator it = mp.begin(); it!=mp.end(); it++){
            if((it->second)>=n){
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Office Keys
题意：有n个人，m个keys，目的地p，每个人要拿一个keys到达p，没走1m花费1个单位时间，问所有人到达p的最小时间
解法1：首先考虑这是在直线上，从最左边的人开始枚举，那么为了方便其他人，他所拿的keys一定是尽可能靠左的，所以二分答案 check就行了
解法2：DP。dp[i][j]表示前i个人利用前j把钥匙都走到p的最小时间，直接O(n*k)枚举转移。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int n, k, p, a[maxn], b[maxn];
long long dp[maxn][maxn];
//dp[i][j]表示前i个人利用前j把钥匙都走到p的最小时间
int main()
{
    while(~scanf("%d %d %d", &n, &k, &p))
    {
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(int i=1; i<=k; i++) scanf("%d", &b[i]);
        sort(a+1,a+n+1);
        sort(b+1,b+k+1);
        memset(dp, 0x3f, sizeof(dp));
        for(int i=0; i<=k; i++) dp[0][i] = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=k; j++){
                long long dis = abs(a[i]-b[j])+abs(b[j]-p);
                dp[i][j] = dp[i][j-1];
                dp[i][j] = min(dp[i][j], max(dp[i-1][j-1],dis));
            }
        }
        printf("%lld\n", dp[n][k]);
    }
    return 0;
}

E. Cards Sorting

题意：有n张卡片，成一个队列，每次操作如果队头是队列中最小的就拿出去，否则放到队尾。问等队列为空操作了多少次？
解法：
其实就是个模拟。

但是直接模拟复杂度是O(n2)的显然不可取
然后考虑如何维护。
首先由于有删除点，首先想到SPLAY维护，将该删除的删除，或者放到意义上的最后。
每次找当前意义上对头后面的最近的最小值
复杂度大概是O(nlognlogn) 而且实现起来有一定难度，
然后想每一次删除相当于存在，或者不存在，想到用BIT维护即可求意义上的两次删点的操作次数。
找最小值，看到1e6的范围想到桶排，然后同样大小的要记录位置，所以开vector数组即可
维护一个意义上队头，然后二分找那个位置最近。不断维护即可
复杂度是O(nlogn)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
namespace BIT{
    int c[maxn];
    void init(){
        memset(c, 0, sizeof(c));
    }
    int lowbit(int x){
        return x&-x;
    }
    void update(int x, int val){
        for(;x<maxn;x+=lowbit(x)) c[x] += val;
    }
    int query(int x){
        int ret = 0;
        while(x>0){
            ret+=c[x];
            x-=lowbit(x);
        }
        return ret;
    }
    int query(int l, int r){
        if(l>r) return query(r)+query(maxn) - query(l-1);
        else return query(r)-query(l-1);
    }
};
using namespace BIT;
vector <int> pos[maxn];
int n, x, nowpos, nxtpos;
LL ans;
int main(){
    while(~scanf("%d", &n)){
        init();
        for(int i=0; i<maxn; i++) pos[i].clear();
        for(int i=1; i<=n; i++){
            scanf("%d", &x);
            pos[x].push_back(i);
            update(i,1);
        }
        nowpos = ans = 0;
        for(int i=1; i<maxn; i++){
            if(pos[i].size()){
                nxtpos = lower_bound(pos[i].begin(), pos[i].end(), nowpos) - pos[i].begin();
                if(nxtpos == pos[i].size()) nxtpos = 0;
                for(int j=0; j<pos[i].size(); j++){
                    ans += query(nowpos, pos[i][nxtpos]);
                    update(pos[i][nxtpos],-1);
                    nowpos = pos[i][nxtpos];
                    nxtpos++;
                    if(nxtpos == pos[i].size()) nxtpos = 0;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

F. Bamboo Partition

题意：有n个植物，最开始均为0米。每天长1米。可以认为修剪，且修建后植物不生长。每隔d天需要人去修剪照看。问你在剪下去的长度和小于k的情况下 d最大为多少，看了这个题解：http://blog.csdn.net/qq_33184171/article/details/75138225

核心式子就是 d<=(k+∑ni=1a[i])∑ni=1ceil(a[i]d)

那么直接枚举 (k+∑ni=1a[i]) 的约数就可以可以了。

代码1：按照上面题解的方法维护

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, k, a[110];

int main(){
    while(~scanf("%lld%lld", &n,&k)){
        LL s = 0, ans = -1;
        for(int i=1; i<=n; i++){
            scanf("%lld", &a[i]);
            s += a[i];
        }
        sort(a+1, a+n+1);
        for(int i=1; i<=n; i++) a[i]--;
        LL d2 = (s+k)/n;
        if(d2 > a[n]) ans = max(ans, d2);
        for(LL d=1, r; d<=a[n]; d=r+1){
            r = a[n];
            LL s1 = 0;
            for(int j=1; j<=n; j++){
                s1 += a[j]/d+1;
                if(a[j]/d) r = min(r, a[j]/(a[j]/d));
            }
            LL d1 = min(r, (s+k)/s1);
            if(d1 >= d) ans = max(ans, d1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

代码2：按照第二种理解的方法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans, tot, n;
LL a[105];
void update(LL d)
{
    LL sum = 0;
    for(int i = 1; i <= n; i++)
        sum += (a[i] - 1) / d + 1;
    if(sum * d <= tot)
        ans = max(ans, d);
}
int main()
{
    LL k;
    scanf("%lld %lld", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        tot += a[i];
    }
    tot += k;
    for(LL i = 1; i * i <= tot; i++)
    {
        update(i);
        update(tot / i);
    }
    printf("%lld\n", ans);
    return 0;
}