A : Online Shopping (读懂题即可)
package AtCoder.begin332;
import java.util.Scanner;
public class A {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), s = sc.nextInt(), k = sc.nextInt();
int[] p = new int[n + 10], q = new int[n + 10];
for (int i = 1; i <= n; i ++ ) {
p[i] = sc.nextInt();
q[i] = sc.nextInt();
}
long ans = 0;
for (int i = 1; i <= n; i ++ ) ans += (long) p[i] * q[i];
if (ans >= s) System.out.println(ans);
else System.out.println(ans + k);
}
}
B : Glass and Mug (读懂题然后模拟即可)
package AtCoder.begin332;
import java.util.Scanner;
public class B {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt(), g = sc.nextInt(), m = sc.nextInt();
int ng = 0, nm = 0;
for (int i = 1; i <= k; i ++ ) {
if (ng == g) ng = 0;
else if (nm == 0) nm = m;
else {
ng += nm;
if (ng >= g) {
nm = ng - g;
ng = g;
} else nm = 0;
}
}
System.out.println(ng + " " + nm);
}
}
C : T-shirts (读清题意然后求解即可)
package AtCoder.begin332;
import java.util.Scanner;
public class C {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
String s = sc.next();
int np = 0, nl = 0;
int ans = 0;
for (int i = 0; i < s.length(); i ++ ) {
if (s.charAt(i) == '0') {
ans = Math.max(ans, Math.max(np - m, 0) + nl);
np = 0;
nl = 0;
} else if (s.charAt(i) == '1') np ++ ;
else nl ++ ;
}
ans = Math.max(ans, Math.max(np - m, 0) + nl);
System.out.println(ans);
}
}
D : Swapping Puzzle (枚举全排列 + 求逆序数)
package AtCoder.begin332;
import javax.swing.plaf.nimbus.State;
import java.util.*;
public class D {
/**
* 思路比较简单 :
* 因为交换相邻的行和相邻的列其实就等同于随意交换 -> 可以自己试一试
* dfs枚举行和列的全排列, 然后判断每一个状态的 a 是否和 b 相同
* 相同了如何更新答案 -> 这个状态的交换次数就是行排列和列排列的逆序数之和
*
* 实现过程被edu了 :
* 不必真的取交换, 直接记录行号和列号, 然后到时候根据行号和列号去原数据查就好了
* 因为交换行和交换列是互不影响的
*
* 总结 :
* dfs还是需要多练习一下, 光有思路无法实现是最难受的
* */
static int[][] a, b;
static int[] ri, wi;
static int n, m, ans = Integer.MAX_VALUE;
static Set<Integer> sr = new HashSet<>();
static Set<Integer> sw = new HashSet<>();
private static void init() {
a = new int[n + 10][m + 10];
b = new int[n + 10][m + 10];
ri = new int[n + 10]; // 记录行当前的排列
wi = new int[m + 10]; // 记录列当前的排列
}
private static void dfs_row(int u) { // 枚举行的全排列
if (u > n) dfs_col(1);
for (int i = 1; i <= n; i ++ ) {
if (sr.contains(i)) continue;
ri[u] = i;
sr.add(i);
dfs_row(u + 1);
sr.remove(i);
}
}
private static void dfs_col(int u) { // 枚举列的全排列
if (u > m) {
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (a[ri[i]][wi[j]] != b[i][j]) return ; // 不符合要求
// 算出这个状态的答案
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ )
if (ri[i] > ri[j]) res ++ ;
for (int i = 1; i <= m; i ++ )
for (int j = i + 1; j <= m; j ++ )
if (wi[i] > wi[j]) res ++ ;
ans = Math.min(ans, res); // 尝试更新答案
return ;
}
for (int i = 1; i <= m; i ++ ) {
if (sw.contains(i)) continue;
wi[u] = i;
sw.add(i);
dfs_col(u + 1);
sw.remove(i);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); m = sc.nextInt();
init();
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
a[i][j] = sc.nextInt();
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
b[i][j] = sc.nextInt();
dfs_row(1);
if (ans == Integer.MAX_VALUE) System.out.println(-1); // 无解
else System.out.println(ans);
}
}