- Дорогой, а ты ку
Форумчанин
Регистрация: 06.10.2012
Сообщений: 181
|
java
исправьте алгоритм
Код:
mport java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Locale;
import java.util.Map;
public class game_is {
StreamTokenizer in;
PrintWriter out;
HashMap<Character, Long> m;
public game_is() {
Locale.setDefault(Locale.US);
try {
in = new StreamTokenizer(new BufferedReader(new FileReader((new File("input.txt")))));
out = new PrintWriter(new File("output.txt"));
}
catch (Exception e) {
e.printStackTrace();
}
}
static void add(HashMap<Character, Long> m, char c, long d) {
Long i = m.get(c);
if (i == null)
i = new Long(0);
m.put(c, i + d);
}
void solve() {
tryblock:
try {
in.nextToken(); int n = (int) in.nval;
if (n == 1) {
out.println(0);
out.println(1);
out.close();
break tryblock;
}
char[] a = new char[n];
for (int i = 0; i < n; i++) {
in.nextToken(); a[i] = in.sval.charAt(0);
}
int nmax = 0;
long max = 0;
m = new HashMap<Character, Long>();
add(m, a[0], 1);
add(m, a[1], -1);
int i = 2;
int j = n - 1;
HashMap<Character, Long> s = new HashMap<Character, Long>();
add(s, a[1], 1);
while (i <= j) {
add(s, a[j], i - 1);
if (i == j)
break;
add(m, a[j], 1);
add(s, a[i], i);
add(m, a[i], -1);
i++;
j--;
}
for (i = 0; i < n; i++) {
long r = 0;
for (Map.Entry<Character, Long> e : s.entrySet())
r += Math.abs(e.getKey() - a[i]) * e.getValue();
if (max < r) {
max = r;
nmax = i;
}
for (Map.Entry<Character, Long> e : m.entrySet())
add(s, e.getKey(), e.getValue());
add(m, a[(i + 1) % n], 2);
add(m, a[(i + 1 + n / 2) % n], -1);
add(m, a[(i + 1 + (n + 1) / 2) % n], -1);
}
out.println(max);
out.println(nmax + 1);
out.close();
}
catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
new Thread(new Runnable() {
public void run() {
game_is solution = new game_is();
solution.solve();
}
}).start();
}
}
}вот моё решение
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Locale;
import java.util.Map;
public class game_is {
public game_is{
StreamTokenizer in;
PrintWriter out;
HashMap<Character, Long> m;
public game_is() {
Locale.setDefault(Locale.US);
try {
in = new StreamTokenizer(new BufferedReader(new FileReader((new File("input.txt")))));
out = new PrintWriter(new File("output.txt"));
}
catch (Exception e) {
e.printStackTrace();
}
}
static void add(HashMap<Character, Long> m, char c, long d) {
Long i = m.get(c);
if (i == null)
i = new Long(0);
m.put(c, i + d);
}
void solve() {
tryblock:
try {
in.nextToken(); int n = (int) in.nval;
if (n == 1) {
out.println(0);
out.println(1);
out.close();
break tryblock;
}
char[] a = new char[n];
for (int i = 0; i < n; i++) {
in.nextToken(); a[i] = in.sval.charAt(0);
}
int nmax = 0;
long max = 0;
m = new HashMap<Character, Long>();
add(m, a[0], 1);
add(m, a[1], -1);
int i = 2;
int j = n - 1;
HashMap<Character, Long> s = new HashMap<Character, Long>();
add(s, a[1], 1);
while (i <= j) {
add(s, a[j], i - 1);
if (i == j)
break;
add(m, a[j], 1);
add(s, a[i], i);
add(m, a[i], -1);
i++;
j--;
}
for (i = 0; i < n; i++) {
long r = 0;
for (Map.Entry<Character, Long> e : s.entrySet())
r += Math.abs(e.getKey() - a[i]) * e.getValue();
if (max < r) {
max = r;
nmax = i;
}
for (Map.Entry<Character, Long> e : m.entrySet())
add(s, e.getKey(), e.getValue());
add(m, a[(i + 1) % n], 2);
add(m, a[(i + 1 + n / 2) % n], -1);
add(m, a[(i + 1 + (n + 1) / 2) % n], -1);
}
out.println(max);
out.println(nmax + 1);
out.close();
}
catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
new Thread(new Runnable() {
public void run() {
game_is solution = new game_is();
solution.solve();
}
}).start();
}
}
}
недогоняю
___________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE] (это кнопочка с решёточкой #)
Не забывайте об этом!
Модератор.
Последний раз редактировалось Serge_Bliznykov; 25.10.2012 в 14:56.
|