問題描述
Given n elements, which have two properties, say Property A and Property B. For convenience, we use two integers Ai
and Bi
to measure the two properties.
Your task is, to partition the element into two sets, say Set A and Set B , which minimizes the value of max(x∈Set
A) {Ax}+max(y∈Set
B) {By}.
See sample test cases for further details.
輸入
There are multiple test cases, the first line of input contains an integer denoting the number of test cases.
For each test case, the first line contains an integer N, indicates the number of elements. (1 <= N <= 100000)
For the next N lines, every line contains two integers Ai and Bi indicate the Property A and Property B of the ith element. (0 <= Ai, Bi <= 1000000000)
輸出
For each test cases, output the minimum value.
樣例輸入
1
3
1 100
2 100
3 1
樣例輸出
Case 1: 3
題意：找出一個最大的和最小，
思路：先排序，然後枚舉即可，，
AC代碼：
[cpp]
#include<iostream>
#include<string.h>
#include<cstdio>
#include<memory.h>
#include<algorithm>
#include<vector>
#define N 100005
using namespace std;
typedef struct node
{
__int64 x;
__int64 y;
}Node;
Node s1[N];
bool cmp2(Node xx,Node yy)
{
return xx.y>yy.y;
}
int main() www.2cto.com
{
int T;
scanf("%d",&T);
for(int k=1;k<=T;++k)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%I64d%I64d",&s1[i].x,&s1[i].y);
sort(s1,s1+n,cmp2);
__int64 minx=s1[0].y;
__int64 p=-1;
for(int i=1;i<n;++i)
{
if(s1[i-1].x>p) p=s1[i-1].x;
s1[i].y+=p;
if(s1[i].y<minx) minx=s1[i].y;
}printf("Case %d: %I64d\n",k,minx);
}return 0;
}
[cpp] view plaincopy
基本信息
#: 7214
題目: 1198
提交人: pursuit
語言: G++
提交時間 2012-07-14 09:34:28
作者：smallacmer
