G - Quadcopter Competition

题意：

求从一个点出发，绕着一根旗走，然后回到原点形成一个闭合的回路所需要的最少步数。

思路：

找出出发点到棋子周围8个点的最小距离s，答案是s * 2 + 8。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int a,b;
    int x,y;
    scanf("%d%d",&a,&b);
    scanf("%d%d",&x,&y);
    int ans = 1000;
    for (int i = -1;i <= 1;i++)
    {
        for (int j = -1;j <= 1;j++)
        {
            if (i == 0 && j == 0) continue;
            int tmp = 0;
            tmp += (fabs(a-(x+i)) + fabs(b-(y+j)));
            ans = min(ans,tmp);
        }
    }
    printf("%d\n",ans * 2 + 8);
    return 0;
}

H - Kayaking

题意：

有n条船，其中2条船是单人船，其余的船是双人船。单人船的不稳定性恒为0；双人船的不稳定性为坐在船上的人的体重之差的绝对值。有2 * n个人，要安排全部的人坐到船上，并且使得所有船的不稳定性之和最小。输出这个最小值。

思路：

由于n比较小，所以枚举两个人坐单人船，剩下的人体重排序，一定是体重相邻的人坐一起。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
int a[105];
map<int,int> mp;
int main()
{
    int n;
    scanf("%d",&n);
    n *= 2;
    int ans = 1000000;
    for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
    for (int i = 1;i <= n;i++) mp[a[i]]++;
    for (int i = 1;i <= n;i++)
    {
        for (int j = i + 1;j <= n;j++)
        {
            int b[105];
            int num = 0;
            mp[a[i]]--;
            mp[a[j]]--;
            for (auto it = mp.begin();it != mp.end();++it)
            {
                int v = it -> first;
                int cnt = it -> second;
                while (cnt)
                {
                    cnt--;
                    b[++num] = v;
                }
            }
            sort(b+1,b+1+num);
            int tmp = 0;
            for (int i = 1;i <= num;i += 2)
            {
                tmp += b[i+1] - b[i];
            }
            ans = min(ans,tmp);
            mp[a[i]]++;
            mp[a[j]]++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

I - Jury Meeting

题意：

有n+1座城市，下标0-n。其中1-n每座城市都有一位委员。他们现在要一起集中到城市0，持续k天，然后再飞回各自的城市。有若干航班，每个航班要么是到0，要么是从0出发到其他城市，并且每个航班都是当天出发当天到达。每个航班有一定的花费。现在要求能够让他们在0集中k天，最后回到自己的城市的最小花费。到达或者回去的当天不算在k天之中。

思路：

这个题目是这个专题当中最难的题目（当之无愧。

首先很明显的想法是可以求出每一天全部人都到0城市的最小花费，不满足就赋值为INF；同样，可以计算出每一天所有人都返回到所在城市的最小花费，不满足也赋值为INF。

现在就是要求出某一天当所有人都到达0后，假设这一天为x，总花费为a，在x + 1 + k及其之后的所有天当中，回去的花费最小的，假设为b，那么就是求a + b的最小值。

朴素的想法是$n ^ 2$枚举，但是时间复杂度肯定爆炸。那么想一想优化，嗯，可以用线段树（但是我不会啊

其实还有一种很显然的想法，如果第一天所有人都到了，花费为x，那么第二天肯定是满足所有人都到了的条件，假设第二天花费为y（可以与x不同，想一想，为什么？），那么前两天所有人都到的花费肯定是$min(x,y)$，同理前三天所有人的花费就是min(前两天所有人的最小花费，第三天的花费)。所以用前缀和维护即可。前缀和是什么？（我也不知道

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll inf = 1e16;
struct node
{
    int loc,cost;
    node(){};
    node(int x,int y)
    {
        loc = x;
        cost = y;
    }
};
int a[N],b[N];
ll sa[N],sb[N];
ll pre[N],sub[N];
vector<node> st[N];
vector<node> en[N];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int mx = 0;
    for (int i = 0;i < m;i++)
    {
        int d;
        int de,ar;
        int c;
        scanf("%d%d%d%d",&d,&de,&ar,&c);
        mx = max(d,mx);
        if (de == 0)
        {
            en[d].push_back(node(ar,c));
        }
        else
        {
            st[d].push_back(node(de,c));
        }
    }
    int cnt = 0;
    ll sum = 0;
    for (int i = 1;i <= mx;i++)
    {
        for (auto x : st[i])
        {
            int loc = x.loc;
            int cost = x.cost;
            if (a[loc])
            {
                if (a[loc] > cost)
                {
                    sum -= a[loc];
                    sum += cost;
                    a[loc] = cost;
                }
            }
            else
            {
                cnt++;
                a[loc] = cost;
                sum += a[loc];
            }
        }
        if (cnt >= n)
        {
            sa[i] = sum;
        }
        else
        {
            sa[i] = inf;
        }
    }
    sum = 0;
    cnt = 0;
    for (int i = mx;i >= 1;i--)
    {
        for (auto x : en[i])
        {
            int loc = x.loc;
            int cost = x.cost;
            if (b[loc])
            {
                if (b[loc] > cost)
                {
                    sum -= b[loc];
                    sum += (b[loc] = cost);
                }
            }
            else
            {
                cnt++;
                b[loc] = cost;
                sum += b[loc];
            }
        }
        if (cnt >= n)
        {
            sb[i] = sum;
        }
        else
        {
            sb[i] = inf;
        }
    }
    pre[0] = inf;
    for (int i = 1;i <= mx;i++)
    {
        pre[i] = min(pre[i-1],sa[i]);
    }
    sub[mx+1] = inf;
    for (int i = mx;i >= 1;i--)
    {
        sub[i] = min(sub[i+1],sb[i]);
    }
    ll ans = inf;
    for (int i = 1;i + k + 1 <= mx;i++)
    {
        ans = min(ans,pre[i] + sub[i+k+1]);
    }
    if (ans >= inf) return 0*puts("-1");
    printf("%lld\n",ans);
    return 0;
}

J - Add All

题意：

求把n个数字相加的代价的总和的最小值。每两个数字相加的代价是两个数字的和。

思路：

优先队列，每次取出最小的两个数字相加即可。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > pq;
int main()
{
    int n;
    while (~scanf("%d",&n) && n)
    {
        while (!pq.empty()) pq.pop();
        ll ans = 0;
        for (int i = 0;i < n;i++)
        {
            int x;
            scanf("%d",&x);
            pq.push(x);
        }
        while (pq.size() > 1)
        {
            ll x = pq.top();
            pq.pop();
            ll y = pq.top();
            pq.pop();
            ans += x;
            ans += y;
            pq.push(x+y);
        }
        printf("%lld\n",ans);
    }
    return 0;
}