三角形的优雅值(map和哈希表)

给你 n 个三角形,每个三角形有一个优雅值,
然后给出一个询问,每次询问一个三角形,
求与询问的三角形,相似的三角形中的优雅值最大是多少。
★数据输入
第一行输入包括 n 一个数字,
接下来 n 行,每行四个整数数字
a,b,c,val 表示三条边,以及优美值
之后输入一个数字 m
之后 m 行,每行三个数字 a,b,c,表示询问的三角形。
★数据输出
输出 m 行,如果查询的三角形不在给定的 n 个中,输出”Sorry”,否则输出三角
形的优美值

20
Sorry
5

★提示
给出的三条边无序,且保证可以构成三角形
40%数据
不需要考虑相似条件
70%的数据
1<=n,m<=1,000
1<=a,b,c<=1,000
100%的数据
1<=n<=200,000 1<=m<=500,000
a,b,c(1<=a,b,c<=100,000)
val 在 int 范围内

 

 

知识1:相似三角形的判断: 将其都化成最小的整数相似三角形，如6,8,10化为3，4，5

解法一：用map，搜索比hash表慢

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <string>
using namespace std;
map<__int64,int> mp;
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int n,m,a[5],val,i,t,k,hash;
scanf("%d",&n);
mp.clear();
for(i=0;i<n;i++)
{
scanf("%d %d %d %d",&a[0],&a[1],&a[2],&val);
k = gcd(a[0],gcd(a[1],a[2]));
a[0]/=k;a[1]/=k;a[2]/=k;
sort(a,a+3);
hash = (a[0]*1000000 +a[1])*1000000 + a[2];
if(mp.find(hash) != mp.end())
mp[hash] = max(mp[hash],val);
else
mp[hash] = val;
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d %d %d",&a[0],&a[1],&a[2]);
k = gcd(a[0],gcd(a[1],a[2]));
a[0]/=k;a[1]/=k;a[2]/=k;
sort(a,a+3);
hash = (a[0]*1000000 +a[1])*1000000 + a[2];
if(mp.find(hash) != mp.end())
printf("%dn",mp[hash]);
else
printf("Sorryn");
}
return 0;
}

解法2：用hash表做

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <string>
using namespace std;
struct Node {
__int64 hash;
int val;
}tri[200007];
int gcd(int a,int b)
{
return b ? gcd(b, a % b) : a;
}
bool cmp(Node a, Node b)
{
if (a.hash != b.hash) return a.hash < b.hash;
else return a.val > b.val;
//hash值相等时按val值排序 
}
int Lower_bound(Node *array, int size, int key)
{
int first = 0, middle;
int half, len;
len = size;
while(len > 0) {
half = len >> 1;
middle = first + half;
if(tri[middle].hash < key) {
first = middle + 1;
len = len-half-1;
//在右边子序列中查找

}
else
len = half;
//在左边子序列（包含middle）中查找

}
return first;
}
int main()
{
int n,m,a[5],val,i,t,k;
__int64 hash;
scanf("%d",&n);
//mp.clear();
for(i=0;i<n;i++)
{
scanf("%d %d %d %d",&a[0],&a[1],&a[2],&val);
k = gcd(a[0],gcd(a[1],a[2]));
a[0]/=k;a[1]/=k;a[2]/=k;
sort(a,a+3);
hash = (a[0]*1000000 +a[1])*1000000 + a[2];
tri[i].hash = hash;
tri[i].val = val;
}
sort(tri,tri+n,cmp);
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d %d %d",&a[0],&a[1],&a[2]);
k = gcd(a[0],gcd(a[1],a[2]));
a[0]/=k;a[1]/=k;a[2]/=k;
sort(a,a+3);
hash = (a[0]*1000000 +a[1])*1000000 + a[2];
int pos = Lower_bound(tri,n,hash);
if (pos == n || tri[pos].hash != hash) puts("Sorry");
else printf("%dn", tri[pos].val);
}
return 0;
}