import java.util.*;public class Billionaires { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Map<String, List<Billionaire>> billionairesByCity = new HashMap<>(); for (int i = 0; i < n; i++) { String name = sc.next(); String city = sc.next(); long fortune = sc.nextLong(); Billionaire billionaire = new Billionaire(name, city, fortune); if (!billionairesByCity.containsKey(city)) { billionairesByCity.put(city, new ArrayList<>()); } billionairesByCity.get(city).add(billionaire); } int m = sc.nextInt(); int k = sc.nextInt(); for (int i = 0; i < k; i++) { int day = sc.nextInt(); String name = sc.next(); String city = sc.next(); List<Billionaire> billionaires = billionairesByCity.get(city); for (Billionaire billionaire : billionaires) { if (billionaire.name.equals(name)) { billionaire.addTravel(day); break; } } } List<String> cities = new ArrayList<>(billionairesByCity.keySet()); Collections.sort(cities); for (String city : cities) { List<Billionaire> billionaires = billionairesByCity.get(city); Map<Integer, Long> wealthByDay = new HashMap<>(); for (Billionaire billionaire : billionaires) { for (int day : billionaire.travels) { wealthByDay.put(day, wealthByDay.getOrDefault(day, 0L) + billionaire.fortune); } } int maxDays = 0; for (int day : wealthByDay.keySet()) { long wealth = wealthByDay.get(day); for (int i = day + 1; i <= m; i++) { long futureWealth = wealthByDay.getOrDefault(i, 0L); if (futureWealth > wealth) { break; } if (i - day > maxDays) { maxDays = i - day; } } } if (maxDays > 0) { System.out.println(city + " " + maxDays); } } } static class Billionaire { String name; String city; long fortune; List<Integer> travels = new ArrayList<>(); public Billionaire(String name, String city, long fortune) { this.name = name; this.city = city; this.fortune = fortune; } public void addTravel(int day) { travels.add(day); } }}的计算复杂度是多少
时间: 2024-01-18 14:03:09 浏览: 119
java代码-import java.util.Scanner;
5星 · 资源好评率100%
该程序的计算复杂度是 O(nklogk),其中 n 是亿万富翁的数量,k 是每个亿万富翁旅行的次数的最大值,m 是最大旅行天数。这是由于程序需要对亿万富翁按照城市进行分组,然后对于每个城市,需要计算出每个亿万富翁在每一天的财富总和,并找到每个亿万富翁旅行后能够连续增加财富的最长天数。在计算每个亿万富翁在每一天的财富总和时,需要遍历其旅行的天数,因此时间复杂度为 O(nklogk)。
阅读全文