【题目描述】
寒枫将军将要带领他的部队去圣雪山消灭那里的冰龙。
部队分成了若干个小队，属于同一个小队的人兵种相同。寒枫将军有着杰出的指挥能力，在战斗的时候，寒枫将军能够让所有相同兵种的人互相配合，使t个相同兵种的人发挥出t的战斗力；寒枫将军还能让不同兵种的人互相配合，使整个部队的战斗力是所有兵种战斗力的和。
例如，部队中有3个小队，分别是5个人的步兵小队，3个人的步兵小队，3个人的骑兵小队。那么步兵战斗力为64，骑兵战斗力为9，部队总战斗力为73。
寒枫将军需要知道他的部队的战斗力是多少。
【输入格式】
第一行一个整数n，表示小队数。接下来n行，第i行有两个整数a、b，表示这个小队有a个人，兵种为b。
【输出格式】
一行一个整数，部队的战斗力。
【样例输入】
3
5 1
3 1
3 2
【样例输出】
73
【数据规模与约定】
10%的数据，n=1
30%的数据，n≤1000
另有20%的数据，a=1
另有30%的数据，b≤1000
100%的数据，1≤n≤100000，1≤a≤10000，1≤b≤1,000,000,000
直接用map做就可以。
题解：是以b为关键字排序，然后捋一遍求出答案。时间复杂度（O（nlogn））
代码实现：
我的：
#include<map>
#include<cstdio>
#include<iostream>
using namespace std;
int n,l,s[],b;
long long a,ans;
map <int,long long> v;
int main(){
freopen("expedition.in","r",stdin);
freopen("expedition.out","w",stdout);
cin>>n;
for(int i=;i<n;i++){
cin>>a>>b;
if(!v[b]) s[l++]=b;
v[b]+=a;
}
for(int i=;i<l;i++) ans+=v[s[i]]*v[s[i]];
cout<<ans<<endl;
return ;
}
std：
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = ;
int n;
struct Info
{
int num,kind;
}xu[N];
bool cmp(Info x,Info y)
{
return(x.kind<y.kind);
}
int main()
{
freopen("expedition.in","r",stdin);
freopen("expedition.out","w",stdout);
int i;
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d%d",&xu[i].num,&xu[i].kind);
sort(xu+,xu+n+,cmp);
long long ans=;
for(i=;i<=n;i++)
{
long long now=xu[i].num;
while(i<n && xu[i].kind==xu[i+].kind)
{
i++;
now+=xu[i].num;
}
now*=now;
ans+=now;
}
printf("%I64d\n",ans);
return ;
}
大概敲了不到半个小时，可以接受。