Codeforces Round #318

A. Bear and Elections

每次通过优先队列选取最大的数值，并与第一个人的票数l进行比较，大于l，自减1，并记录大于1的次数即为需要更改票数的人数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()

const int inf = (l << ) - ;
const int maxn = (int)  + ;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b)) 
using namespace std;
int n = , l = ;
int ans = ;
int main()
{
    //freopen("data_A.txt", "r", stdin);
    priority_queue<int> s;
    ans = ;
    scanf("%d%d", &n, &l);
    for (int i = ; i < n; i++)
    {
        int a = ;
        scanf("%d", &a);
        s.push(a);
    }
    while(s.top() >= l)
    {
        l++;
        int a = ;
        a = s.top() - ;
        s.pop();
        s.push(a);
        ans++;
    }
    printf("%d\n", ans);
    return ; 
}
           

再或者手写优先队列：每次找出数组中的最大值：

#include<iostream>
#include<fstream>
using namespace std;
int n = , a[];
int rec = , ans = ;
int main()
{
    //freopen("data_A.txt", "r", stdin);
    while(scanf("%d", &n) != EOF)
    {
        ans = ;
        for (int i = ; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        while(true)
        {
            rec = ;
            for (int i = ; i < n; i++)
            {
                if (a[i] >= a[rec])
                {
                    rec = i;
                }
            }
            if (rec == ) break;
            a[]++;
            a[rec]--;
            ans++;
        }
        printf("%d\n", ans);
    }
    return ;
}
           

B. Bear and Three Musketeers

n个人里面选三个人，除了这三个人之外， 求其他的有多少个人认识这三个人。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()

const int inf = (l << ) - ;
const int maxn = (int)  + ;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b)) 
using namespace std;
int n = , m = , matrix[][], indegree[]; 
int main()
{
    //freopen("data_B.txt", "r", stdin);
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(matrix, , sizeof(matrix));
        memset(indegree, , sizeof(indegree));
        for (int i= ; i < m; i++)
        {
            int a = , b = ;
            scanf("%d%d", &a, &b);
            matrix[a][b] = ;
            matrix[b][a] = ;
            indegree[a]++;
            indegree[b]++;
        }
        int ans = inf;
        for (int i = ; i <= n; i++)
        {
            for (int j = i + ; j <= n; j++)
            {
                if (matrix[i][j])
                {
                    for (int k = j + ; k <= n; k++)
                    {
                        if (matrix[i][k] && matrix[j][k])
                        {
                            ans = min (ans, indegree[i] + indegree[j] + indegree[k]);

                        }
                    }
                }
            }
        } 
        if (ans == inf)
        {
            printf("-1\n");
        }else
        {
            printf("%d\n", ans - );
        }
    }
    return ; 
}
           

C. Bear and Poker

递归实现超时，只有改用其他方法。改成非递归的方式。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()

const int inf = (l << ) - ;
const int maxn = (int)  + ;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b)) 
using namespace std;
int n = , a[]; 
int main()
{
    //freopen("data_C.txt", "r", stdin);
    while(scanf("%d", &n) != EOF)
    {
        for (int i = ; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        for (int i = ; i < n; i++)
        {
            while (a[i] %  == )
            {
                a[i] /= ;
            }
            while (a[i] %  == )
            {
                a[i] /= ;
            }
        }
        for (int i = ; i < n; i++)
        {
            if (a[i] != a[])
            {
                printf("No\n");
                return ;
            } 
        }
        printf("Yes\n");

    } 
    return ; 
}
           

D. Bear and Blocks

动态规划：从左到右以及从右到左进行遍历，找出其中的最小值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()

const int inf = (l << ) - ;
const int maxn = (int)  + ;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b)) 
using namespace std;
int l[], r[], dp[], ans = ;
int n = ;
int d[];
int main()
{
    //freopen("data_D.txt", "r", stdin);
    while(scanf("%d", &n) != EOF)
    {
        ans = ;
        for (int i = ; i < n; i++)
        {
            scanf("%d", &d[i]);
        }
        l[] = ;
        r[n - ] = ;
        for (int i = ; i < n; i++)
        {
            l[i] = min (l[i - ] + , d[i]);
        }
        for (int i = n - ; i > -; i--)
        {
            r[i] = min (r[i + ] + , d[i]);
        }
        for (int i = ; i < n; i++)
        {
            dp[i] = min (l[i], r[i]);
        }
        for (int i = ; i < n; i++)
        {
            ans = max (ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return ; 
}