首页 > > 程序设计 > C/C++ >

UVALive 6911---Double Swords(贪心+树状数组（…

2018-06-17 23:39:17来源：未知阅读 ()

题目链接

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4923

problem description

Last night, Kingdom of Light was attacked by Kingdom of Dark! The queen of Kingdom of Light, Queen Ar, was captured and locked inside a dark and creepy castle. The king of Kingdom of Light, King Ash, wants to save the queen. The castle is guarded by N dragons, conveniently numbered from 1 to N. To save Queen Ar, King Ash must kill all the dragons. The kingdom’s oracle said that in order to kill the i-th dragon, King Ash has to slay it with exactly two swords, one in each hand: one sword of length Ai units, and another sword of length between Bi and Ci , inclusive. King Ash can carry unlimited number of swords, and each sword can be used multiple times. The number of blacksmiths in the kingdom is limited, so it is important to make as few swords as possible. Besides, making swords is expensive and takes much time. Determine the minimum number of swords the kingdom has to make so that King Ash can save Queen Ar!

Input

The first line of input contains an integer T (T ≤ 20) denoting the number of cases. Each case begins with an integer N (1 ≤ N ≤ 100, 000) denoting the number of dragons which have to be killed. The next N lines each contains three integers: Ai , Bi , and Ci (1 ≤ Ai ≤ 1, 000, 000; 1 ≤ Bi ≤ Ci ≤ 1, 000, 000) denoting the swords’ length needed to kill the i-th dragon as described in the above problem statement.

Output

For each case, output ‘Case #X: Y ’, where X is the case number starts from 1 and Y is the minimum number of swords the kingdom has to make and carry in order to defeat all the dragons and save Queen Ar.

Explanation for 1st sample case: The kingdom has to make two swords in order to defeat one dragon.

Explanation for 2nd sample case: All the dragons can be defeated by three swords, for example, with lengths of: 3, 6, and 15.

• The fist dragon can be defeated by swords of length 3 and 6.

• The second dragon can be defeated by swords of length 6 and 15.

• The third dragon can be defeated by swords of length 3 and 15.

There also exists other combination of three swords.

Sample Input

7 6 8

3 5 10

6 11 15

3 13 15

1 10 20

3 50 60

2 30 40

4 70 80

5 100 200

150 1000 2000

Sample Output

Case #1: 2

Case #2: 3

Case #3: 8

Case #4: 3

题意：有n条恶龙，需要人同时持两把剑杀死，一把剑要求长为A，另一把剑长度在B~C之间，输入n条龙的A B C数据要求，求最少需要携带多少把剑？

思路：对于n组恶龙的数据，按照C的大小从左到右排序。先考虑数据A，即先把长度固定的剑需要的数量确定，有些A相同只计算一次，sum=0，sum+=unique（Ai）。然后考虑长度为区间（B~C）的剑，对于排好序的数据，循环处理，对于区间Bi~Ci 如果区间里没有剑或者有一把剑且长度和Ai相等，则添加一把剑长为Ci，sum++，这样可能在后面的区间中出现，使得剑的数量最少，否则不处理，表明这个区间中有剑，不需要加入剑。注意：在判断区间中剑的数量时，用树状数组很方便查询；

代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
const int maxn=1e6+5;
int c[maxn];
bool vis[maxn];
struct Node
{
    int x,y;
    int z;
}node[2*100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
int Lowbit(int t)
{
    return t&(t^(t-1));
}
void add(int x)
{
    while(x<maxn){
        c[x]++;
        x+=Lowbit(x);
    }
}
int sum(int x)
{
    int sum=0;
    while(x){
        sum+=c[x];
        x-=Lowbit(x);
    }
    return sum;
}
int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(c,0,sizeof(c));
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            if(!vis[node[i].z]){
                add(node[i].z);
                vis[node[i].z]=true;
            }
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        for(int i=0;i<N;i++)
        {
            int t=sum(node[i].y)-sum(node[i].x-1);
            if(t==1&&node[i].z>=node[i].x&&node[i].z<=node[i].y)
                add(node[i].y);
            else if(!t) add(node[i].y);
        }
        printf("Case #%d: %d\n",Case++,sum(maxn-1));
    }
    return 0;
}

这题也可以用集合，其实和上面思路差不多，用集合判断区间中是否有剑；

在网上看到有人用set写，代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
struct Node
{
    int x,y;
    int z;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
set<int>s;
set<int>::iterator it;

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        s.clear();
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            s.insert(node[i].z);
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        int sum=0;
        for(int i=0;i<N;i++)
        {
            it=s.lower_bound(node[i].x);
            if(it!=s.end()&&*it==node[i].z) it++;
            if(it==s.end()||*it>node[i].y){
                if(node[i].z==node[i].y)
                    s.insert(0-node[i].y);
                   //sum++;///set有去重功能;
                else  s.insert(node[i].y);
            }
        }
        printf("Case #%d: %d\n",Case++,s.size()+sum);
    }
    return 0;
}

这样写确实AC了，但我感觉有BUG 我认真看了程序，想了一个数据：

4 2 4

4 4 6

正确答案是2

运行这个程序结果是3

但是用多重集合是可以避免这个BUG的

代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
const int maxn=1e6+5;
bool vis[maxn];
struct Node
{
    int x,y;
    int z;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
multiset<int>s;
multiset<int>::iterator it;

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        s.clear();
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            if(!vis[node[i].z]){
                s.insert(node[i].z);
                vis[node[i].z]=true;
            }
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        for(int i=0;i<N;i++)
        {
            it=s.lower_bound(node[i].x);
            if(it!=s.end()&&*it==node[i].z) it++;
            if(it==s.end()||*it>node[i].y){
                s.insert(node[i].y);
            }
        }
        printf("Case #%d: %d\n",Case++,s.size());
    }
    return 0;
}
/*
345
2
4 2 4
4 4 6
2
4 2 4
4 3 4
*/