勇者斗恶龙（Dragon of Loowater ,UVa 11292)

题目链接

https://vjudge.net/problem/UVA-11292

题意

将题目抽象化得：
给定一个含有n个数的数组a和一个含有m个数的数组b。
问对于a数组的每一个元素是否在b数组中都唯一存在一个比其大的元素？
如果存在，输出所有对应元素的和（要求最小）；
如果不存在，输出“Loowater is doomed!”。

题解

显然，当n大于m时，输出“Loowater is doomed!”。
对于a数组中的元素x，从b数组中找一个刚好大于等于x的值是最优的。STL中lower_bound()函数能很好的实现这一点（自己用二分实现也可以）。问题的关键变成了如何确定唯一性，定义一个vis数组来表示该元素有无被占用过即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=2e4+100;
int l[maxn],a[maxn],vis[maxn];

int main()
{
    int n,m,ok;
    while(~scanf("%d%d",&n,&m))
    {
        memset(l,0,sizeof(l));
        memset(a,0x7f,sizeof(a));
        memset(vis,0,sizeof(vis));
        ok=1;
        if(n==0 && m==0) break;
        for(int i=0; i<n; i++)
            scanf("%d",&l[i]);
        for(int i=0; i<m; i++)
            scanf("%d",&a[i]);
        if(n>m)
        {
            printf("Loowater is doomed!\n");
            continue;
        }

        sort(l,l+n);
        sort(a,a+m);
        int t=n,ans=0;
        while(t--)
        {
            int pos=lower_bound(a,a+m,l[t])-a;
            while(vis[pos] && a[pos]!=a[maxn-1]) pos++;

            if(a[pos]==a[maxn-1])
            {
                printf("Loowater is doomed!\n");
                ok=0;
                break;
            }
            else
            {
                vis[pos]=1;
                ans+=a[pos];
            }

        }
        if(ok)
            printf("%d\n",ans);

    }
    return 0;
}