中南大学第十一届大学生程序设计竞赛-COJ1900-锋芒不露

60 阅读 0 评论 40 点赞

我是靠谱客的博主简单月饼，最近开发中收集的这篇文章主要介绍中南大学第十一届大学生程序设计竞赛-COJ1900-锋芒不露，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1900: 锋芒不露

Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 13 Solved: 4
Description
小闪最近迷上了二刀流——不过他耍的其实是剑——新买了一个宝库用来专门存放自己收集的双剑。一对剑有两把，分只能左手用的和只能右手用的，各自有一个攻击力数值。虽然一对剑在小闪刚拿到时是一对，不过其实可以认为它们是独立的两把剑。一对剑的攻击力是左右两把剑的攻击力之和，小闪可以自由地搭配左右剑来练习二刀流。每次小闪得到一对新的双剑，他都可以去更新一次自己的双剑宝库，重新给每把剑配对。小闪需要自己给每一把剑配对，然后他的智能宝库会提供宝库中攻击力最高的一对剑来给小闪练习；不过小闪其实是一个很低调的人，不喜欢锋芒毕露，希望自己练习时的双剑攻击力尽可能小——虽然不知道怎么改变宝库，但是他可以改变双剑的搭配。每次新得到一对剑，更新完宝库之后，小闪练习时用的剑可能就会发生变化。请你求出每次更新宝库后小闪练习二刀流时的双剑攻击力。

Input
输入包含不超过10组数据。对于每组数据，第一行一个整数N(1<=N<=100000)，表示小闪前后共收集到了N对双剑；接下来N行，每行包含两个整数A和B（1<=A,B<=100），分别表示每次小闪收集到的一对剑的左手用剑和右手用剑的攻击力数值。每组数据之后会有一个空行。输入以一行一个整数0结束。

Output
对于每组数据，输出N行，每行一个整数，表示每次更新后小闪练习二刀流时的双剑攻击力值。相邻两组数据之间输出一个空行。

Sample Input
3
2 8
3 1
1 4

3
1 1
2 2
3 3

0
Sample Output
10
10
9

2
3
4
Hint
Source
中南大学第十一届大学生程序设计竞赛

题目大意：每次给你一个左手剑的值和右手剑的值，让你重新放入仓库中，将之间所有的左右手剑重新匹配，然后从里面获得合并后最大价值的一组剑，且希望这个值尽可能小。
解题思路：这题目我们可以很明显地发现如果左手剑的数值是L[1…n]，右手剑的数值是R[1…n]。
如果希望匹配的结果是最大值尽可能的小，那么一定是最大的L和最小的R匹配，然后次大的L和次小的R匹配，然后依次匹配下去，匹配过程中得到的最大值就是答案。
但是这样的复杂度是O(n^2)的。明显是不行的。
这里有一点是会发现剑的值不超过100，所以可以作为数组下标，用一个数组记录每种值存在多少把剑，左手从小到大，右手从大到小，不断交替减掉匹配的个数，更新当前匹配的最大值。
考察内容：贪心、计数
时间复杂度： O(100n)
题目难度： ★★★

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
int L[105],R[105];

int main()
{
    int n;
    int a,b;
    int Max;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        int lm=100,rm=0;
        for(int k=1;k<=n;k++)
        {
            scanf("%d%d",&a,&b);
            L[a]++;R[b]++;
            if(lm>a) lm=a;
            if(rm<b) rm=b;
            Max=0;
            int i=lm,j=rm;
            int p=L[lm],q=R[rm];
            int match=0;
            while(match!=k)
            {
                if(p==0) {p=L[++i];continue;}
                if(q==0) {q=R[--j];continue;}
                if((i+j)>Max) Max=i+j;
                if(p==q)
                {
                    match+=p;
                    i++;j--;
                    p=L[i];q=R[j];
                }else if(p<q)
                {
                    q-=p;
                    match+=p;
                    p=L[++i];
                }else if(p>q)
                {
                    p-=q;
                    match+=q;
                    q=R[--j];
                }
            }
            printf("%dn",Max);
        }
        printf("n");
    }
    return 0;
}