漫画网站建设教程,第一网站ppt模板,青岛中英网站建设,百度排名点击器题目
古人云#xff1a;秀恩爱#xff0c;分得快。
互联网上每天都有大量人发布大量照片#xff0c;我们通过分析这些照片#xff0c;可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人#xff0c;这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在…题目
古人云秀恩爱分得快。
互联网上每天都有大量人发布大量照片我们通过分析这些照片可以分析人与人之间的亲密度。如果一张照片上出现了 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题解编者的错解能过一半后一半其中一个错误其他超时不知道为什么错误没想到什么极端样例能让其不过思想和下面给出的正解几乎一致
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;/*** author akuya* create 2023-10-31-15:15*/
public class love {static int N1005;static double arr[][]new double[N][N];static int sex[]new int[N];static int n,m;static PriorityQueueInteger lpqnew PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return Math.abs(o1)-Math.abs(o2);}});static PriorityQueueInteger opqnew PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return Math.abs(o1)-Math.abs(o2);}});public static void main(String[] args) throws IOException {BufferedReader brnew BufferedReader(new InputStreamReader(System.in));String nm[]br.readLine().split( );nInteger.parseInt(nm[0]);mInteger.parseInt(nm[1]);while(m--!0){String kn[]br.readLine().split( );int kInteger.parseInt(kn[0]);for(int i1;ik;i){for(int ji1;jk;j){int xInteger.parseInt(kn[i]);int yInteger.parseInt(kn[j]);int axMath.abs(x);int ayMath.abs(y);if(kn[i].charAt(0)-){sex[ax]-1;}else{sex[x]1;}if (kn[j].charAt(0)-) {sex[ay]-1;}else{sex[y]1;}double ans(double)1/k;arr[ax][ay]ans;arr[ay][ax]ans;}}}String lo[] br.readLine().split( );int lInteger.parseInt(lo[0]);int oInteger.parseInt(lo[1]);int alMath.abs(l);int aoMath.abs(o);double lmax-1;double omax-1;for(int i0;in;i){if(l*sex[i]0){if(arr[al][i]lmax){lpq.clear();lpq.add(sex[i]*i);lmaxarr[al][i];}else if(arr[al][i]lmax){lpq.add(sex[i]*i);}}}for(int i0;in;i){if(o*sex[i]0){if(arr[ao][i]omax){opq.clear();opq.add(sex[i]*i);omaxarr[ao][i];}else if(arr[ao][i]omax){opq.add(sex[i]*i);}}}if(lpq.contains(o)opq.contains(l)){System.out.println(l o);return;}while(!lpq.isEmpty()){System.out.println(l lpq.poll());}while(!opq.isEmpty()){System.out.println(o opq.poll());}}
}
正解
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** author akuya* create 2023-11-01-11:57*/
public class Main {static int N1005;static ListInteger tree new ArrayList();static int n,flag0;static int a[]new int[N];public static void main(String[] args) {Scanner scannernew Scanner(System.in);nscanner.nextInt();for(int i1;in;i) a[i]scanner.nextInt();creat(1,n);if(tree.size()!n){flag1;tree.clear();creat(1,n);}if(tree.size()n){System.out.println(YES);int lentree.size();int log1;for(int i:tree){if(loglen){System.out.println(i);}elseSystem.out.print(i );log;}}else System.out.println(NO);}public static void creat(int root,int last){if(rootlast) return;int leftroot1;int rightlast;if(flag0){while(leftlasta[left]a[root]) left;while(rightroota[right]a[root]) --right;}else{while(leftlasta[left]a[root]) left;while(rightroota[right]a[root]) --right;}if(right!(left-1)) return;creat(root1,right);creat(left,last);tree.add(a[root]);}}
思路
这道题的思路挺简单就是用一个动态数组存储照片中的人用一个数组存储性别然后n2遍历即可做出。
