垃圾装袋(标记法)

                                              问题 G: 垃圾装袋(点击跳转)

                                                                   时间限制: 1 Sec  内存限制: 128 MB
                                                                                 提交: 360  解决: 84
                                                                    [提交] [状态] [讨论版] [命题人:admin]

题目描述

某城市环卫部门需要对分布在城市中不同地点的 n 堆(编号为 1 到 n)垃圾进行装袋处 理。现在有 m 个(编号为 1 到 m)垃圾袋可以使用。 

一个容量为 v 的垃圾袋能装入不超过容量为 v 的垃圾,一堆垃圾要求只能用一个垃圾 袋来装,一个垃圾袋也只能用来装一堆垃圾(即一个垃圾袋不能在两个地方装垃圾)。一个 垃圾袋的价格是由垃圾袋的容量来决定,容量为 v 的垃圾袋价格为 v。 

请编程帮环卫部门计算要将 n 堆垃圾全部装袋,用掉的垃圾袋最少值多少钱? 

 

 

输入

输入共 3 行。 
第 1 行两个正整数 n 和 m,表示需要处理 n 堆垃圾,现在有 m 个垃圾袋。 第 2 行 n 个整数,依次表示每堆垃圾的容量。 
第 3 行 m 个整数,依次表示每个垃圾袋的容量。 

 

 

输出

输出共 1 行。 输出一个整数,如果能将所有的垃圾装入已有的袋子,则输出用掉的垃圾袋最少值多少 

钱?如果无法将所有的垃圾装入 m 个袋子,则输出“-1”。 

 

样例输入

复制样例数据

3 4
3 6 4
4 5 7 3

样例输出

14

 

提示

有3堆垃圾,4个袋子,第1堆容量为3的垃圾用第4个容量为3的袋子装,第2堆容 
量为6的垃圾用第3个容量为7的袋子装,第3堆容量为4的垃圾用第1个容量为4的袋子 装,所以用掉的垃圾袋最少值3+7+4=14。

30%的测试点输入数据保证1≤n,m≤1000 
70%的测试点输入数据保证1≤n,m≤10000 
100%的测试点输入数据保证1≤n,m≤50000,每个垃圾袋的容量和每处垃圾的容量 不超过10000。 

代码:

#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(long long int a,long long int b)
{
    return a<b;
}
int main()
{
    long long int a[50006],b[50006],flag[50006]={0},n,m,i,j,count,sum;
    scanf("%lld%lld",&n,&m);      //输入数据
    for(i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    for(i=0;i<m;i++){
        scanf("%lld",&b[i]);
    }
    sort(a,a+n,cmp);          //sort对两组数据从小到大排序
    sort(b,b+m,cmp);
    j=0,sum=0,count=0;
    for(i=0;i<n;i++){          //for循环垃圾堆 
        for(j=j;j<m;j++){        //for循环垃圾袋
            if(a[i]<=b[j]){
                flag[i]=1;    //装过垃圾后将i标记 便于查看是否还剩垃圾没有装完 从而输出-1
                sum+=b[j++];
                break;
            }
        }
    }
    for(i=0;i<n;i++){
        if(flag[i]==1){         //循环标记的数组 查看是否满足条件(将所有的垃圾堆装完)
            count++;
        }
    }
    if(count==n)
        printf("%lld\n",sum);
    else
        printf("-1\n");
    return 0;
}