ACM本周作业的记录-创新互联

这次我格某人没有在拖了。这次因为上次V50的教训让我不敢再拖着不写了，那么开始题吧

输入 #1

6 
5 28 16 29 27 
23 3 20 1 
8 32 26 
33 11 
12

输出 #1

1
32

输入 #2

8 
42 24 10 29 27 12 58 
31 8 16 26 80 6 
25 3 36 11 5 
33 20 17 13 
15 77 9 
4 50 
19

输出 #2

1
77

【数据范围】

对于40%的数据有N≤10。

对于70%的数据有N≤18。

对于100%的数据有N≤500。

这题，看看题，感觉需要模拟，但是大致写了代码框架，发现模拟至少要写三重循环，而500次，三重循环，可能会超时（虽然不确定）而且还有递归，实现比较复杂，想想这肯定不是最好的办法，但是我也想不来最好的办法，于是只能求助了。

  这题其实是个博弈论问题，诸如此类的问题时不需要用代码来模拟实现游戏的过程的。由于计算机总是倾向于破坏最好的组合，所以你肯定是不能拿到最好的组合的。也就是说每组能产生默契值大的组合，一个人在你这，另一个人，在计算机这，你们都拿不到最好的组合。这时候你只要拿到每组次大组合中的最佳选项，那么你就是胜券在握了。

再从出题人的角度出发，我们做题都是要不择手段的。如果我们不一定会赢，那么我们只需要输出0就可以了，也就是说无脑cout<< 0<< endl;就能骗过一部分的测试数据。如果是某些赛制的比赛，那么就可以得到一部分的得分。可事实上，出题人会让你那么好骗数据吗？当然不会，所以，从这个层面来讲，我们人是必赢的。

  接着就是上代码了，贪心算法就是这样子，题目搞会了代码就是轻轻松松简简单单的。同时复习下外挂函数sort的使用方法。

//三国游戏
#includeusing namespace std;
const int MAX = 502;
int vec[MAX][MAX] = {0};        //用来存放武将之间的关系
int n;                          //用来存放武将的数目
int main()
{
    cin >>n;
    for(int i = 1; i<= n; i++)
    {
        for(int j = i+1; j<= n; j++)
        {
            cin >>vec[i][j];
            vec[j][i] = vec[i][j];  //双向存储会好一些
        }
    }
    int ans = 0;
    for(int i = 1; i<= n; i++)
    {
        sort(vec[i]+1, vec[i]+n+1, greater()); //来排序了，从大到小排序
        //从大到小排序的方法第一是greater()
        //第二种是用兰木达表达式
        //第三种是函数名字传参
        // for(int j = 1; j<= n; j++)
        // {
        //     cout<< vec[i][j]<< ' ';
        // }
        ans = max(ans, vec[i][2]);
    }
    cout<< 1<< endl<< ans;
    return 0;
}

两个整数有一个空格符分开

输入 #1

4
2
1 3

输出 #1

2 4

对于 100% 的数据，满足初始时，没有两个士兵同在一个坐标，1≤L≤5×10^3，0≤N≤5×10^3，且数据保证 N≤L。

  上一题够无语了，这题就是更加无语。本来不看题解想着模拟这些人的行动真心好复杂啊，这么多人，每个人的方向不一样，这不是关键，关键是，人与人还有碰撞，看到题解的灵魂交换这个词恍然大悟，其实两个人相向而行和发生碰撞后回头对于这个整体来说其实是等效的，这就是我们灵魂交换的合理之处。也就是说不管是哪个人，但是我们只要知道有个人在那个位置就足够判断了。也就是说直接让人横穿就行了。知道了这个之后，代码就没那么难了。最长的情况就是每个人都往最长的方向走，取路径最长。最短的情况就是每个人往最短的方向走，取最长（让每个人下桥才行啊）

#includeusing namespace std;

int main()
{
    int L;          //桥的长度
    cin >>L;
    int N;          //人的个数
    cin >>N;
    int max_ans = 0, min_ans = 0;
    for(int i = 1; i<= N; i++)
    {
        int X;
        cin >>X;
        max_ans = max(max_ans, max(X, L+1-X));
        min_ans = max(min_ans, min(X, L+1-X));
    }
    cout<< min_ans<< ' '<< max_ans<< endl;
    return 0;
}

输入 #1

10 
56 12 1 99 1000 234 33 55 99 812

输出 #1

3 2 7 8 1 4 9 6 10 5
291.90

n≤1000,ti​≤10^6，不保证ti​ 不重复。

当 ti​ 重复时，按照输入顺序即可（sort 是可以的）

这个题是小学的题，只要优先选择接水时间短的人来接水就可以完成任务的。用代码实现就可以了。题目的提示说了sort可以，那就sort呗。

注意下每个人接水的时间不是自己等待的时间，第一个人接水时n-1个人在等待。

这题的坑点主要在于当用int存储总时间时可能会越界，而我还没有看出来（感觉自己退化了）

这时候要么老老实实用double存储总时间，要么#define int long long（真的好无耻的做法，尽量别用）double能精确存储的整数位数long long是可以存储的

#includeusing namespace std;
struct person
{
    int num;        //编号
    int time;       //接水的时间，注意不是他自己的等待时间
};
int main()
{
    int N;
    cin >>N;
    vectorarr(N+1);    //数列呗
    for(int i = 1; i<= N; i++)
    {
        int time;
        cin >>time;
        arr[i].time = time;
        arr[i].num = i;         //加入这个人
    }
    //排序
    sort(arr.begin()+1, arr.end(), [](const person &p1, const person &p2)
    {
        return p1.time< p2.time;
    });
    double sum = 0;
    for(int i = 1; i<= N; i++)
    {
        if(i != 1)
            cout<< ' ';
        cout<< arr[i].num;
        sum += arr[i].time*(N-i);
    }
    printf("\n%.2lf\n", sum/N);
}

我们的final boss终于要献身了，这题的标签最多的，但是选对外挂也是最简单的。

输入 #1

3 
1 2 9

输出 #1

15

对于 30% 的数据，保证有 n≤1000：

对于 50% 的数据，保证有 n≤5000；

对于全部的数据，保证有 n≤10000。

  这一题最初一眼看来，这不就是哈夫曼树吗？于是复习了哈夫曼树后就来做这题，结果，不出所料，运行超时，，，吃席打脸时刻！！！

  原来还有优先队列这种玩意啊，不得不说stl的外挂真的是太牛了！

  下面简单介绍下优先队列，priority_queue，只要#include里面绝对会有这个东东的。和普通的队列一样，队列前面的先出去，只不过可以自动排序哦，就是自动把优先级高的放在队头，优先级低的压在队尾，是不是很强大的啊？

  priority_queue, greater>que;就是定义一个优先队列，但是greater是小的元素在队头，而lesser是大的元素在队头，这个怎么和sort是反过来的啊，奇怪

  就用优先队列就行，每次从队头拿出两个，在队尾插进一个，他会自己排好序的，直到队列只有一个元素为止，这样子就可以搞定了。把注释去掉，发现代码其实不长的，很容易过的。

#includeusing namespace std;
//感觉这题像哈夫曼树
// struct node
// {
//     int value;                  //当前节点值
//     int parent;                 //双亲结点
//     int lchild;                 //左孩子
//     int rchild;                 //右孩子
// };
// //选择，最小的节点和第二小的节点
// void select(vectorhftree, int size, int &f1, int &f2)
// {
//     int min1 = 0, min2 = 0;
//     for(int i = 1; i<= size; i++)  //在现今的范围内寻找
//     {
//         if(hftree[i].value< hftree[min1].value && !hftree[i].parent)
//         {
//             min1 = i;
//         }
//     }
//     for(int i = 1; i<= size; i++)
//     {
//         if(hftree[i].value< hftree[min2].value && i != min1 && !hftree[i].parent)
//         {
//             min2 = i;
//         }
//     }
//     f1 = min1, f2 = min2;
// }
int main()
{
    int n;
    cin >>n;
    // vectorarr(n);
    // vectorhftree(2*n);    //事实上节点数目只有2*n-1
    // hftree[0].value = INT_MAX;
    // hftree[0].parent = 0;           //头结点的初始化，用于比较
    // for(int i = 0; i< n; i++)
    // {
    //     cin >>arr[i];
        // hftree[i].value = arr[i];
        // hftree[i].parent = 0;
        // hftree[i].lchild = 0;
        // hftree[i].rchild = 0;       //先初始化
    // }
    priority_queue, greater>que;         //从小到大的优先队列


    for(int i = 0; i< n; i++)
    {
        int t;
        cin >>t;
        que.push(t);                                         //加入t
    }
    //从n+1开始，在前面寻找
    int ans = 0;
    // for(int i = n+1; i<= 2*n-1; i++)
    // {
    //     int min1, min2;
    //     select(hftree, i-1, min1, min2);
    //     hftree[min1].parent = i;    //设置双亲
    //     hftree[min2].parent = i;    //设置左右孩子
    //     hftree[i].lchild = min1;
    //     hftree[i].rchild = min1;
    //     hftree[i].value = hftree[min1].value + hftree[min2].value;
    //     ans += hftree[i].value;
    // }
    while(que.size() >1)
    {
        int t1 = que.top(), t2;
        que.pop();
        t2 = que.top();
        que.pop();
        que.push(t1+t2);
        ans += t1+t2;
    }
    cout<< ans<< endl;
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧