OpenJudge:冷血格斗场

OpenJudge:冷血格斗场"/>

OpenJudge:冷血格斗场

题目描述

/

题目思路

• 这道题看着简单，但是有很多坑
• 要考虑实力差相等的时候取id比较小的对手
• 要考虑时间复杂度，下面我的第一种解法就TLE了

解法一
二维数组存id和实力值，基本上是O(n*n)的时间复杂度，但是测试用例中的100000组输入，代码超时
#include <iostream>
#include<math.h>
#include <fstream> 
using namespace std;
#define N 100001
int a[N][2],fight[N];
int main() {freopen("in.txt","r",stdin);int n;cin>>n;a[0][0]=1,a[0][1]=1000000000;for(int i=1;i<=n;i++){cin>>a[i][0]>>a[i][1];}for(int i=1;i<=n;i++){int min=a[0][1];for(int j=i-1;j>=0;j--){if(abs(a[i][1]-a[j][1])<=min){//不能忽略实力值相等 if(abs(a[i][1]-a[j][1])==min){if(a[j][0]<fight[i]){//实力差相等，取id小的 fight[i]=a[j][0];}}else{min=abs(a[i][1]-a[j][1]);fight[i]=a[j][0];}}}}for(int i=1;i<=n;i++){cout<<a[i][0]<<" "<<fight[i]<<endl;     }fclose(stdin);return 0;
}
解法二
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
map<int,int>a;  //实力值，ID
map<int,int>::iterator it;
int n,x,pw;
int main()
{freopen("in.txt","r",stdin);a[1000000000]=1;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&x,&pw);it=a.lower_bound(pw);if(it==a.end()) it--;int idx=it->second;int pw1=abs(it->first-pw);if(it!=a.begin()){it--;if(abs(it->first-pw)<pw1||(pw1==abs(it->first-pw)&&it->second<idx))idx=it->second;}printf("%d %d\n",x,idx);it=a.find(pw);if(it==a.end()||it->second>x)a[pw]=x; }fclose(stdin);return 0;
}