Решение математической задачи «Мишка и путешествие» - C#
Формулировка задачи:
Маленькая Мишка — большая путешественница. В каких только странах она не побывала! После долгих раздумий о том, куда бы поехать в этом году, выбор её пал на XXX — прекрасную, но малоизвестную северную страну.
Вот несколько интересных фактов об этой стране:
В состав XXX входят n городов, k из которых (только представьте себе!) являются столицами.
Все города этой страны красивы, но по-разному. Красота i-го города описывается величиной ci.
Все города последовательно соединены дорогами, включая 1-й и n-й город, образуя замкнутый маршрут 1 — 2 — ... — n — 1. Формально, для каждого 1 ≤ i < n существует дорога между городами i и i + 1, и еще одна между городами 1 и n.
Каждый город-столица напрямую соединен дорогами со всеми остальными городами. Формально, если город x — столица, то для каждого 1 ≤ i ≤ n, i ≠ x, существует дорога между городами x и i.
Между любыми двумя городами существует не более одной дороги.
Стоимость проезда между городами напрямую зависит от показателей их красоты. Так, если между городами i и j существует дорога, то стоимость проезда по ней равна ci·cj.
Мишка уже начала собираться в путешествие, но ещё не определилась со своим маршрутом, а потому попросила вас помочь ей оценить суммарную стоимость проезда по всем дорогам XXX. Формально, по всем различным парам городов a и b (a < b), таких, что a и b соединены дорогой, требуется посчитать сумму произведений ca·cb. Поможете ей?
Входные данные
В первой строке входных данных содержатся числа n и k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n) — количество городов в XXX и количество столиц среди них соответственно. Во второй строке содержится n целых чисел c1, c2, ..., cn (1 ≤ ci ≤ 10 000) — показатели красоты каждого из городов. В третьей строке содержится k различных целых чисел id1, id2, ... idk (1 ≤ idi ≤ n) — номера городов, являющихся столицами. Номера городов заданы в порядке возрастания.Выходные данные
Выведите единственное целое число — суммарную стоимость проезда по всем существующим дорогам в XXX.Решение задачи: «Решение математической задачи «Мишка и путешествие»»
textual
Листинг программы
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { InputReader in = new InputReader(System.in); //InputReader in = new InputReader(new FileInputStream("input.txt")); Task solver = new Task(); solver.solve(in); } } class Task { public static final int MAXN = 100003; public void solve(InputReader in) throws IOException { int n = in.readInt(); int k = in.readInt(); long[] beauty = new long[MAXN]; long beautySum = 0; for (int i = 0; i < n; ++i) { beauty[i] = in.readLong(); beautySum += beauty[i]; } long cost = 0; Set<Integer> caps = new HashSet<>(); while (k-- > 0) { int cap = in.readInt() - 1; cost += beauty[cap] * (beautySum - beauty[cap]); beautySum -= beauty[cap]; caps.add(cap); } for (int i = 0, j = 1; i < n; ++i, j = (j + 1) % n) { if (!caps.contains(i) && !caps.contains(j)) { cost += beauty[i] * beauty[j]; } } System.out.println(cost); } } class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String readLine() { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } public String readToken() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(readLine()); } return tokenizer.nextToken(); } public int readInt() { return Integer.parseInt(readToken()); } public long readLong() { return Long.parseLong(readToken()); } public double readDouble() { return Double.parseDouble(readToken()); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д