Решение математической задачи «Мишка и путешествие» - 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());
}
}