2015
04-13

# hdu 3877-special sort-排序-[解题报告]hoj

Problem Description
We all know a+b=c,but now there is a new rule in equations:

if a>b,then it’s equal to [>c];
if a=b,then it’s equal to [=c];
if a<b,then it’s equal to [<c];
a sample:

1+1=[=2]
2+0=[>2]
0+2=[<2]
1+2=[<3]

and [>c] > [=c] > [<c].
For every [n],
[n+1] > [n] >[n-1].

Input
The input consists of T cases.The first line of the input contains only positive integer T (0<T<=100).Then follows the cases.Each case begins with a line containing exactly one integer N (0<N<=10000).Then there are N lines, each with
two integers a and b (0<a,b<2^31-1).

Output
For each case, calculate each value of a+b(as a+b=[?]) and output a+b=[?] in descending order sorted by [?]. If there exists some pair of a,b whose order can not be determined by the rules above, output them with the order of the
input. A blank line should be printed after each case.

Sample Input
2 5 1 5 5 1 3 3 4 5 5 6 5 1 6 6 1 2 4 4 2 3 3

Sample Output
5+6=[<11] 4+5=[<9] 5+1=[>6] 3+3=[=6] 1+5=[<6] 6+1=[>7] 1+6=[<7] 4+2=[>6] 3+3=[=6] 2+4=[<6]

Source

#include<stdio.h>
#include<algorithm>
typedef long long ll;

using namespace std;

struct node
{
ll a;
ll b;
ll ans;
ll level;
};
node E[10005];

bool cmp(node x,node y)
{
if((x.ans>y.ans)||(x.ans==y.ans&&x.level>y.level))
return true;
return false;
}

int main()
{
ll t,n,i;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d",&n);
for(i=1;i<=n;i++)
{
scanf("%I64d%I64d",&E[i].a,&E[i].b);
E[i].ans=E[i].a+E[i].b;
if(E[i].a>E[i].b)
E[i].level=3;
else if(E[i].a==E[i].b)
E[i].level=2;
else
E[i].level=1;
}
stable_sort(E+1,E+1+n,cmp);
for(i=1;i<=n;i++)
{
if(E[i].level==3)
printf("%I64d+%I64d=[>%I64d]\n",E[i].a,E[i].b,E[i].ans);
if(E[i].level==2)
printf("%I64d+%I64d=[=%I64d]\n",E[i].a,E[i].b,E[i].ans);
if(E[i].level==1)
printf("%I64d+%I64d=[<%I64d]\n",E[i].a,E[i].b,E[i].ans);
}
printf("\n");
}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。