水题系列一：Circle

问题描述：Circle

小明在玩游戏，他正在玩一个套圈圈的游戏。他手里有 L 种固定半径的圆圈，每一种圆 圈都有其固定的数量。他要把这些圆圈套进 N 个圆形槽中的一个。这些圆形槽都有一个最 小半径和最大半径，他要套进去的圆圈半径必须在圈槽的最小半径和最大半径之间（含）。 圆形槽如图所示，绿色部分表示可以放圈圈。这 N 个圆形槽的最小半径和最大半径都不一 样。求最多可以放进去多少个圆圈。每一个圆形槽最多放一个圆圈。

数据输入

第 1 行是两个数 N 和 L。（1<=N,L<=2500） 第 2 行到第 N+1 行每行有两个数字，分别表示每一个圆形槽的最小半径和最大半径。 第 N+2 行到第 N+L+1 行每行有两个数字，分别表示每一种圆圈的半径和这种圆圈的数 量。 半径和圆圈均为 1 到 1000 的整数。 ★结果输出： 输出一个整数 S，表示最多可以放进去的圆圈数。

输入示例

输出示例 3 2 3 10 2 5 1 5 6 2 4 1 2

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<string>

#include<map>

#include<algorithm>

using namespace std;

struct circle

{

    int le,ri;

    int isUsed;

}chao[];

bool compareCircle(struct circle a,struct circle b)

{

    if(a.ri<b.ri)return true;

    if(a.ri==b.ri)return a.le<b.le;

    return false;

}

int main()

{

    int N,L;

    int i;

    scanf("%d%d",&N,&L);

    for(int i=;i<N;i++)

    {

        scanf("%d%d",&chao[i].le,&chao[i].ri);

    }

    sort(chao.chao+N,compareCircle);

    int quan[];

    //init

    for(int i=;i<=;i++)

    {

        quan[i]=;

    }

    for(int j=;j<l;j++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        quan[a]+=b;

    }

    int sum=;

    //以要放入的圆圈为主，去放到槽中

    for(int k=;k<=;k++)

    {

        if(quan[k]==)continue;

        for(int t=;t<N;t++)

        {

            if(chao[t].isUsed==)

            {

                if(chao[t].le<=k&&chao[t].ri>=k)

                {

                    chao[t].isUsed=;

                    sum++;

                    quan[k]--;

                    if(quan[k]==)break;

                }

            }

        }

    }

    printf("%d",sum);

    reurn ;

}