Atcoder B.C.302与R.C.163 （我的复健）メモ
去年下半年工作特忙，和今年前半年也没怎么搞算法，就上班做些常规的工作。
今天周末比较闲，阴天也不太想远走旅行，遂下午预约了个台球练习练习。突然想起来不知道今天有没有Atcoder的比赛，一查21:00有一场。一年多没打了，拿起来找找感觉呗，闲着也是闲着。工作都在写Java，写C++和Python都有点生疏了。
B.C.302 (AtCoder Beginner Contest 308)
A题，简单到写不出题解，题目给三个条件，全符合这三个条件的输入就给输出Yes，否则输出No。
N=8
a=list(map(int,input().split(" ")))
t1 = all(map(lambda x: 100 <=x and x <= 675,a))
t2 = all(map(lambda x: x%25 ==0,a))
b = []
for i in range(N):
b.append(a[i])
b.sort()
Tflag = t1 and t2
for it in zip(a,b):
if( it[0] != it[1]):
Tflag = False
break
print("Yes" if Tflag else "No")B题也是模拟，用个map（Python里的dict），单次检索时间\( O(\log(M)) \) ，总复杂度 \( O(N \log(M)) \)。此题由于数据量不大，据说直接存数组以\( O(MN) \) 的时间也能过
N,M = map(int,input().split(" "))
eat = input().split(" ")
menu = input().split(" ")
priceList =list(map(int, input().split(" ")))
priceKey = {}
for i in range(M):
priceKey[menu[i]] = priceList[i+1]
cost = 0
for it in eat:
if it in priceKey:
cost += priceKey[it]
else:
cost += priceList[0]
print(cost)
C题注意两个点，一个是\( 10^{9} \)的数据量由于要相乘，所以数据需要定义成int64类型的。另一个排序是稳定排序，algorithm库中有个稳定排序std::stable_sort。由于 std::sort 是不稳定排序，用错了就有几个测试点会坏。
include <cstdio>
#include <algorithm>
const int MAXN = 200007;
struct node
{
int id;
// = num/den
long long num;
long long den;
bool operator<(const node &o) const
{
return num*o.den > den * o.num;
}
};
struct node a[MAXN];
int main(void){
int N;
scanf("%d",&N);
long long num,den;
for(int i=0;i<N;++i){
scanf("%lld%lld",&num,&den);
a[i].id = i+1;
a[i].num = num;
a[i].den = den + num;
}
std::stable_sort(a,a+N);
for(int i=0;i<N;++i){
if(i>0)
printf(" ");
printf("%d",a[i].id);
}
printf("\n");
return 0;
}D. 基本的DFS
代码晚上回去写
E.
R.C. 163 (AtCoder Regular Contest 163)
A.看给出的单词是否切分成按严格字典序来排。最小要求切分两个元素，那么就极限法，就切两个，从哪儿切呢，首先第1个字母必是第1个单词的首字母，只要在其后存在比第1个单词的首字母更大的，就从这儿切分，就必然可以组成长度为2的符合字典序的列表。所以问题变成从第2个字母到最末字母查找是否存在比第1个字母的字典序更大的字母，存在则直接输出Yes，否则No
import java.io.BufferedReader;
import java.io.InputStreamReader;
class Main {
public static void main() throws Exception {
BufferedReader bf;
bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
while (T-- > 0) {
int N;
N = Integer.parseInt(bf.readLine());
String msg = bf.readLine();
solve(N, msg);
}
return;
}
private static void solve(int N, String msg) {
for (int i = 1; i < N; i++) {
if (msg.charAt(i) > msg.charAt(0)) {
System.out.println("Yes");
return;
}
}
System.out.println("No");
return;
}
}B. 给出一个序列\( {A_i} \)和正整数M。每次操作可以使\( A_i \) 中的一个元素+1或-1，使至少有M个\(A_i , (3 \le i \le N \)，满足\(A_1 \le A_i \le A_2\)。求最小的操作次数。
由于\(A_1\)和\(A_2\)也是\( \{A_i\} \)，如果\( \{A_i\} , 3 \le i \le N\)中各不相同，则操作哪个的次数都一样。如果 \( \{A_i\} ( 3 \le i \le N )\)中有相同的数字，则使\(A_1\)减小或\(A_2\)增加，相比与操作 \( \{A_i\} , 3 \le i \le N\)相同的数字的次数必然要少。于是可以将问题化为 将 \{A_i\} 排序得到 \{B_i\} 有 \{B_1,B_2, \cdots, B_{i},A_1,\cdots, A_2, B_{j},\cdots,B_N\} ，并随着A_1于是问题可以变为将\( \{A_i\} , 3 \le i \le N\)排序得到\(\{B_1,B_2,\cdots,B_{N-2}\}\)，从中搜每个长为M的区间，计算使\(A_1,A_2\)到这个区间的最小操作次数。复杂度为\(O(N \log N) + O (N) = O( N \log N ) \) -1与A2+1的操作，使A_1与A_2之间的数字有至少M个。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
class Main {
public static void main() throws Exception {
BufferedReader bf;
bf = new BufferedReader(new InputStreamReader(System.in));
String[] line = bf.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int M = Integer.parseInt(line[1]);
int[] arr = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int lwbd = arr[0];
int upbd = arr[1];
int[] b = Arrays.copyOfRange(arr, 2, N);
Arrays.sort(b);
int minOp = 0x7FFFFFFF;
for (int i = 0; i < N - 1 - M; i++) {
minOp = Math.min(minOp, Math.max(0, lwbd - b[i]) + Math.max(0, b[i + M - 1] - upbd));
}
System.out.println(minOp);
return;
}
}
C.调和级数
