problem
L2-028 秀恩爱分得快 (25分) 古人云：秀恩爱，分得快。
互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？
输入格式： 输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：
K P[1] … P[K] 其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。
输出格式： 首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB。但如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。
输入样例 1： 10 4 4 -1 2 -3 4 4 2 -3 -5 -6 3 2 4 -5 3 -6 0 2 -3 2 输出样例 1： -3 2 2 -5 2 -6 输入样例 2： 4 4 4 -1 2 -3 0 2 0 -3 2 2 -3 2 -1 2 -3 2 输出样例 2： -3 2
给出n个人，求一对cp最亲密的异性是谁给出m张照片，每张上的k个人两两亲密度+=1/k
solution
枚举照片，如果出现了cp，累加他们和其他异性的亲密度，排序输出。对于0和-0，把他们转换为1000以上（大于范围就行）BUG了一次，只有15分，改不动了，重新写一遍
#include<bits/stdc++.h>
using namespace std
;
bool cmp(int a
, int b
){
if(abs(a
)==1000)return true;
if(abs(b
)==1000)return false;
return abs(a
)<abs(b
);
}
int main(){
int n
, m
, sex
[1010]={0};
cin
>>n
>>m
;
vector
<vector
<int>>photo(m
);
for(int i
= 0; i
< m
; i
++){
int k
; cin
>>k
;
for(int j
= 0; j
< k
; j
++){
string s
; cin
>>s
;
if(s
=="0")s
="1000";
if(s
=="-0")s
="-1000";
int tmp
= stoi(s
);
photo
[i
].push_back(tmp
);
sex
[abs(tmp
)] = tmp
;
}
}
int cp
[3];
for(int i
= 1; i
<= 2; i
++){
string s
; cin
>>s
;
if(s
=="0")s
="1000";
if(s
=="-0")s
="-1000";
cp
[i
] = stoi(s
);
}
double love
[1010] = {0};
for(int c
= 1; c
<= 2; c
++){
for(int i
= 0; i
< m
; i
++){
int ok
= 0;
for(int j
= 0; j
< photo
[i
].size(); j
++){
if(photo
[i
][j
]==cp
[c
]){
ok
= 1;
break;
}
}
if(ok
){
for(int j
= 0; j
< photo
[i
].size(); j
++){
if(cp
[c
]*photo
[i
][j
]<0){
love
[abs(photo
[i
][j
])] += 1.0/photo
[i
].size();
}
}
}
}
}
double maxx
[3] = {0};
vector
<vector
<int> >ans(3);
for(int c
= 1; c
<= 2; c
++){
for(int i
= 1; i
<= 1000; i
++){
if(cp
[c
]*sex
[i
]<0){
if(love
[i
]>maxx
[c
]){
maxx
[c
] = love
[i
];
ans
[c
].clear();
ans
[c
].push_back(sex
[i
]);
}else if(love
[i
]==maxx
[c
]){
ans
[c
].push_back(sex
[i
]);
}
}
}
}
if(maxx
[1]==love
[abs(cp
[2])] && maxx
[2]==love
[abs(cp
[1])]){
string s1
= to_string(cp
[1]), s2
= to_string(cp
[2]);
if(cp
[1]==1000)s1
="0";
if(cp
[1]==-1000)s1
="-0";
if(cp
[2]==1000)s2
="0";
if(cp
[2]==-1000)s2
="-0";
cout
<<s1
<<" "<<s2
<<endl
;
return 0;
}
for(int c
= 1; c
<= 2; c
++){
sort(ans
[c
].begin(), ans
[c
].end(),cmp
);
for(int i
= 0; i
< ans
[c
].size(); i
++){
string s1
= to_string(cp
[c
]), s2
= to_string(ans
[c
][i
]);
if(cp
[c
]==1000)s1
= "0";
if(cp
[c
]==-1000)s1
= "-0";
if(ans
[c
][i
]==1000)s2
= "0";
if(ans
[c
][i
]==-1000)s2
= "-0";
cout
<<s1
<<" "<<s2
<<endl
;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std
;
bool cmp(pair
<int,double>a
, pair
<int,double> b
){
if(a
.second
!=b
.second
)return a
.second
>b
.second
;
return a
.first
<b
.first
;
}
int main(){
int n
, m
;
cin
>>n
>>m
;
vector
<vector
<int> >photo(m
+1);
for(int i
= 1; i
<= m
; i
++){
int k
; cin
>>k
;
for(int j
= 1; j
<= k
; j
++){
string x
; cin
>>x
;
if(x
=="0")x
= "1000";
if(x
=="-0")x
= "-1000";
photo
[i
].push_back(stoi(x
));
}
}
int cp
[3];
for(int i
= 1; i
<= 2; i
++){
string x
; cin
>>x
;
if(x
=="0")x
= "1000";
if(x
=="-0")x
= "-1000";
cp
[i
] = stoi(x
);
}
double love
[3][1050];
memset(love
,0,sizeof(love
));
for(int i
= 1; i
<= m
; i
++){
for(int c
= 1; c
<= 2; c
++){
int ok
= 0;
for(int j
= 0; j
< photo
[i
].size(); j
++){
if(photo
[i
][j
]==cp
[c
]){
ok
= 1; break;
}
}
if(ok
){
for(int j
= 0; j
< photo
[i
].size(); j
++){
if(cp
[c
]*photo
[i
][j
]<0){
love
[c
][abs(photo
[i
][j
])] += 1.0/photo
[i
].size();
}
}
}
}
}
vector
<pair
<int,double> >ans
[3];
for(int i
= 1; i
<= 1000; i
++){
for(int c
= 1; c
<= 2; c
++){
if(love
[c
][i
]>0){
ans
[c
].push_back(make_pair(i
,love
[c
][i
]));
}
}
}
sort(ans
[1].begin(),ans
[1].end(),cmp
);
sort(ans
[2].begin(),ans
[2].end(),cmp
);
if(abs(ans
[1][0].second
-love
[1][abs(cp
[2])])<0.02 && abs(ans
[2][0].second
-love
[2][abs(cp
[1])])<0.02){
string s1
= to_string(cp
[1]), s2
= to_string(cp
[2]);
if(cp
[1]==1000)s1
="0";
if(cp
[1]==-1000)s1
="-0";
if(cp
[2]==1000)s2
="0";
if(cp
[2]==-1000)s2
="-0";
cout
<<s1
<<" "<<s2
<<endl
;
return 0;
}
for(int c
= 1; c
<= 2; c
++){
for(int i
= 0; i
< ans
[c
].size(); i
++){
if(ans
[c
][i
].second
==ans
[c
][0].second
){
int t
= cp
[c
], tt
= -abs(cp
[c
]*ans
[c
][i
].first
)/cp
[c
];
string ts
= to_string(t
), tts
= to_string(tt
);
if(t
==1000)ts
="0";
if(t
==-1000)ts
="-0";
if(tt
==1000)tts
="0";
if(tt
==-1000)tts
="-0";
cout
<<ts
<<" "<<tts
<<endl
;
}
}
}
return 0;
}
