两段代码，区别：第一段采用sort排序后选取最大值，第二段直接选取最大值。第一段AC第二段超时，sort快排最好情况不会少于O(n),这么说应该是第二个快啊
题目：
Problem Description
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.
Input
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)
Output
For each test cases, output the minimum value.
Sample Input
1
3
1 100
2 100
3 1
Sample Output
Case 1: 3
代码一：
#include
#include
const int N=100005;
using namespace std;
class a
{ public:
__int64 o,p;
};
a t[N];
bool fx(a x,a y)
{
return x.p>y.p;
}
int main()
{
int T,i,k;
scanf("%d",&T);
for(k=1;k<=T;k++)
{
int n;
scanf("%d",&n);
for(i=0;i
scanf("%I64d%I64d",&t[i].o,&t[i].p);
sort(t,t+n,fx);
__int64 min=t[0].p;
__int64 b=-1;
for(i=1;i
{
if(t[i-1].o>b) b=t[i-1].o;
t[i].p+=b;
if(t[i].p<min) min=t[i].p;
}
printf("Case %d: %I64d\n",k,min);
}
return 0;
}
代码二：
#include
#include
using namespace std;
int main()
{
int n;
int k1,k2,k3;
__int64 a[100001],b[100001];
__int64 max1,max2,min;
int x;
scanf("%d",&x);
{
for(int i=1;i<=x;i++)
{
scanf("%d",&n);
for(k1=0;k1<n;k1++)
{
scanf("%I64d%I64d",&a[k1],&b[k1]);
}
min=2000000002;
for(k3=0;k3<n-1;k3++)
{
max1=a[0];
max2=b[k3+1];
for(k2=1;k2<=k3;k2++)
{
if(a[k2]>max1)max1=a[k2];
}
for(k2=k3+2;k2<n;k2++)
{
if(b[k2]>max2)max2=b[k2];
}
if((max1+max2)<min)min=(max1+max2);
}
printf("Case %d: %I64d\n",x,max);
}
}
return 0;
}
谢谢
