1. 计算字典序介于给定的两个字符串之间的字符串的个数。
花了15分钟。一开始想暴力，看了数据规模觉得不行。
public class Main {
public static long helper(String a, String b) {
if (a.compareTo(b) >= 0)
return 0;
int n = a.length();
long res = 0;
long base = 1;
for (int i = n-1; i >= 0; i--) {
int num1 = a.charAt(i) - 'a';
int num2 = b.charAt(i) - 'a';
res += (num2 - num1) * base;
base *= 26;
}
return res - 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
int n = sc.nextInt();
String a = sc.next();
String b = sc.next();
System.out.println(helper(a, b));
}
}
}
2. 有T个案例。每个案例有一个n代表怪兽数量，m代表宝剑耐久度。有n行，每一行是怪兽的hp和杀死后获得的奖励。耐久度高于hp可以杀怪兽。奖励是可以不使用耐久度就可以杀死a个怪兽。对于每一个案例输出最多杀几个，花费的最少的耐久度。
一开始以为必须按顺序杀，浪费不少时间。后来觉得是要排序，贪心算法。反正最后还是没做出来，通过5%，叹气。请大家帮我看看问题。我现在还没想明白我错哪了。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
static long monsters = 0;
static long loss = 0;
public static void helper(ArrayList<Entry> entries, long m, int n) {
int arm = 0;
while (entries.size() > 0) {
boolean found = false;
for (int i = 0; i < entries.size(); i++) {
Entry e = entries.get(i);
if (arm == 0 && e.hp > m)
continue;
//if (arm == 0 && m <= 0) break;
found = true;
if (arm > 0)
arm--;
else {
m -= e.hp;
loss += e.hp;
}
arm += e.arm;
monsters++;
entries.remove(i);
break;
}
if (!found)
return;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
int n = sc.nextInt();
long m = sc.nextLong();
ArrayList<Entry> entries = new ArrayList();
for (int i = 0; i < n; i++) {
long hp = sc.nextLong();
long arm = sc.nextLong();
Entry e = new Entry(hp, arm);
entries.add(e);
}
Collections.sort(entries);
helper(entries, m, n);
System.out.println(monsters + " " + loss);
monsters = 0;
loss = 0;
}
}
}
class Entry implements Comparable<Entry> {
long hp;
long arm;
public Entry(long h, long a) {
hp = h;
arm = a;
}
public int compareTo(Entry e2) {
if (arm != e2.arm)
return Long.compare(e2.arm, arm);
return Long.compare(hp, e2.hp);
}
} 
全部评论
(0) 回帖