mulitset可以当BST用。。。
Time Limit:3000MS |
Memory Limit:Unknown |
64bit IO Format:%lld & %llu |
[Submit] [Go Back] [Status]
Description
Problem I
Efficient Solutions
Input: Standard Input
Output: Standard Output
"Our marriage ceremonies are solemn, sober
moments of reflection; also regret, disagreement,
argument and mutual recrimination. Once you know
it can't get any worse, you can relax and enjoy
the marriage."
|
J. MichaelStraczynski, "The Deconstruction of Falling Stars."
The princess of Centauri Prime is the galaxy's most eligiblebacheloretteof the year. She has hopeful grooms lined up in front of the royal palace for a chance to spend 5 minutes to try and impress her. After 5 minutes, the gentleman is carried out of the
royal chambers by the palace guards, and the princess makes a decision. She rates the lad on his lineage and charm by giving him a score for each of the two properties. On Centauri Prime, low scores are better than high scores.
Suppose that she observes two gentlemen - A and B. She assigns A the scores LAand CA(for lineage and charm, respectively). B receives scores LBand CB. Then A isdominatedby B if either
- LB< LAand CB<= CA, or
- LB<= LAand CB< CA.
In other words, if at least one of B's scores is better than A's, and the other score is not worse. She considers a gentleman to beefficient(or Pareto-optimal) if she has not yet met any other gentleman who dominates him. She maintains alist
of efficient groomsand updates it after each 5-minute presentation.
Given the queue of bachelors and the scores assigned to them by the princess, determine the number of entries in thelist of efficient groomsafter each performance.
Input
Thefirst line of input gives the number of cases,N (0<N<40).Ntest cases follow.
Each one starts with a line containingn(0≤n≤15000) - the size of the queue. The nextnlines will each contain two scores (integers in the range [0, 109]). Initially, the list is empty.
Output
For each test case, output one line containing "Case #x:" followed bynlines, lineicontaining the size of thelist of efficient groomsafter theithupdate. Print an empty line between test cases.
Sample Input
|
Sample Output
|
4
1
100 200
2
100 200
101 202
2
100 200
200 100
5
11 20
20 10
20 10
100 20
1 1
|
Case #1:
1
Case #2:
1
1
Case #3:
1
2
Case #4:
1
2
3
3
1
|
Problemsetter: IgorNaverniouk
Special Thanks:YuryKholondyrev
Warming: The judge input file size is about 1.2 MB.
[Submit] [Go Back] [Status]
|
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;
struct POINT
{
int x, y;
bool operator<(const POINT res) const
{
if (x != res.x)
{
return x < res.x;
}
else
{
return y < res.y;
}
}
}P;
int main()
{
multiset<POINT> msp;
multiset<POINT>::iterator it;
int t,n,cas=1;
scanf("%d",&t);
while(t--)
{
msp.clear();
scanf("%d",&n);
if(cas>1) putchar(10);
printf("Case #%d:\n",cas++);
for(int i=0;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
P=(POINT){a,b};
it=msp.lower_bound(P);
if(it==msp.begin()||(--it)->y>b)
{
msp.insert(P);
it=msp.upper_bound(P);
while(it!=msp.end()&&it->y>=b)
{
msp.erase(it++);
}
}
printf("%d\n",msp.size());
}
}
return 0;
}
分享到:
相关推荐
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva_solutions
Uva-Solutions
UVa solutions. Author: Tianyu Zhang
UVA-解决方案 UVA 解决方案这个代表是我从 uva 尝试的一些代码
#uva解决方案我对一些问题的解决方案我的uHunt个人资料 问题源我要解决的大多数问题-在的《被推荐。在我学习本书时,新的问题得到了解决和补充。 ##便捷工具集我使用### run.sh脚本来编译解决方案,针对测试数据集...
uva272
UVA109的题解,经测试完全正确,还附有题解。