題目鏈接
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
4
1
7 6 8
3
3 5 10
6 11 15
3 13 15
4
1 10 20
3 50 60
2 30 40
4 70 80
2
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 我認真看了程序，想了一個數據：
1
2
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
*/
