tsao

tsao
1个月前
class Solution {
public int maxDistance(int[] a, int m) {
Arrays.sort(a);
int l = 0, r = (int) 1e9;
while(l < r - 1){
int mid = l + r >> 1;
if(check(a, mid, m)) l = mid;
else r = mid;
}
return check(a, l, m) ? l : r;
// return r;
}
private boolean check(int[] a, int mid, int m){
int last = a[0], cnt = 1;
for(int i = 1; i < a.length; i++){
if(a[i] - last >= mid){
cnt++;
last = a[i];
}
}
return cnt >= m;
}
}


tsao
9个月前

    public static void main(String[] args) {
String str = "abbba";
System.out.println (judge (str.toCharArray ()));
int n = str.length (), cnt = 0, minm = Integer.MAX_VALUE;
int swaps = minSwaps (str.toCharArray (), 0, n - 1, cnt, minm);
System.out.print (swaps);
}

// 判断当前字符串是否满足要求：所有相同字符均相邻
static boolean judge(char arr[]) {
int[] idx = new int[26];
Arrays.fill (idx, -1);
for (int i = 0; i < arr.length; i++) {
if (idx[arr[i] - 'a'] == -1 || idx[arr[i] - 'a'] == i - 1) {
idx[arr[i] - 'a'] = i;
} else {
return false;
}
}
return true;
}

static int minSwaps(char str[], int l, int r, int cnt, int minm) {
if (l == r) {
if (judge (str)) {
return cnt;
} else {
return Integer.MAX_VALUE;
}
}
// 从l+1开始，分别递归求l和i交换和不不交换的最小值
for (int i = l + 1; i <= r; i++) {
swap (str, i, l);
int x = minSwaps (str, l + 1, r, cnt+1, minm);

swap (str, i, l);
int y = minSwaps (str, l + 1, r, cnt, minm);

minm = Math.min (minm, Math.min (x, y));
}

return minm;
}


tsao
11个月前

### 题目描述

#### 模板

public class InputTemplate {

static class FR {
StringTokenizer tk;

FR(InputStream stream) {
tk = null;
}

String next() {
while (tk == null || !tk.hasMoreElements ()) {
try {
tk = new StringTokenizer (br.readLine ());
} catch (IOException e) {
e.printStackTrace ();
}
}
return tk.nextToken ();
}

int nextInt() {
return Integer.parseInt (next ());
}
}

static void solve(InputStream stream, PrintWriter out) {
FR in = new FR (stream);

//  start code.....

}

public static void main(String[] args) {
OutputStream os = System.out;
InputStream is = System.in;
PrintWriter out = new PrintWriter (os);
solve (is, out);
out.close (); // 不关闭就没有输出
}
}


#### 题解的全部 Java代码

import java.io.*;
import java.util.*;

class SegTree {
// start 和 end 是区间范围
int start;
int end;
long dat; // 记录的信息（最值，统计值）
long tag; // 懒标记
}

public class Main {
static class FR {
StringTokenizer tk;

FR(InputStream stream) {
tk = null;
}

String next() {
while (tk == null || !tk.hasMoreElements ()) {
try {
tk = new StringTokenizer (br.readLine ());
} catch (IOException e) {
e.printStackTrace ();
}
}
return tk.nextToken ();
}

int nextInt() {
return Integer.parseInt (next ());
}
}
static void solve(InputStream stream, PrintWriter out) {
FR sc = new FR (stream);

//  start code.....
int n = sc.nextInt ();
int m = sc.nextInt ();
int[] arr = new int[n + 1];
SegTree[] tree = new SegTree[n << 2 + 1];
for (int i = 0; i < tree.length; i++) {
tree[i] = new SegTree ();
}
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt ();
}
build_ (arr, tree, 1, 1, n);
while (m-- > 0) {
String str = sc.next ();
int l = sc.nextInt (), r = sc.nextInt ();
if (str.equals ("Q")) {
System.out.println (query_ (tree, 1, l, r));
} else {
int val = sc.nextInt ();
update_ (tree, 1, l, r, val);
}
}

}
public static void main(String[] args) {
OutputStream os = System.out;
InputStream is = System.in;
PrintWriter out = new PrintWriter (os);
solve (is, out);
out.close (); // 不关闭就没有输出
}

// 1. 建树，初始调用 build(1, 1, n);
static void build_(int[] arr, SegTree[] tree, int rt, int l, int r) {
if (l == r) {
tree[rt].dat = arr[l];
tree[rt].start = l;
tree[rt].end = r;
//            System.out.println ("rt:" + rt + " l:" + l + " r:" + r + " " + idx++);
// 单点区间不能再分，递归结束
return;
}

// 递归左右子树
int mid = l + r >> 1;
build_ (arr, tree, rt << 1, l, mid);
build_ (arr, tree, rt << 1 | 1, mid + 1, r);

//回溯时更新
tree[rt].dat = tree[rt << 1].dat + tree[rt << 1 | 1].dat;
tree[rt].start = tree[rt << 1].start;
tree[rt].end = tree[rt << 1 | 1].end;
}

// 2. 懒标记
static void spread_(SegTree[] tree, int rt) {
if (tree[rt].tag != 0) {
int ls = rt << 1, rs = rt << 1 | 1;
long lazy = tree[rt].tag;
// 修改区间信息并更新懒标记
tree[ls].dat += lazy * (tree[ls].end - tree[ls].start + 1);
tree[ls].tag += lazy;

tree[rs].dat += lazy * (tree[rs].end - tree[rs].start + 1);
tree[rs].tag += lazy;

// 大区间信息已经传递给下一层，因此要清零。
tree[rt].tag = 0;
}
}

// 3. 区间修改
static void update_(SegTree[] tree, int rt, int l, int r, int val) {
if (l <= tree[rt].start && r >= tree[rt].end) {
// 如果一个结点表示的区间被修改区间覆盖，那它就是连续区间的一段
// 如果它所包含的小区间都不用修改，只要修改懒标记就行了
tree[rt].dat += val * (tree[rt].end - tree[rt].start + 1);
tree[rt].tag += val;

return;// 因为不用修改，直接返回就行
}
// 保证懒标记只在最新的区间上

int mid = tree[rt].start + tree[rt].end >> 1;

if (l <= mid) update_ (tree, rt << 1, l, r, val);
if (r >= mid + 1) update_ (tree, rt << 1 | 1, l, r, val);

// 递归回溯时修改dat
tree[rt].dat = tree[rt << 1].dat + tree[rt << 1 | 1].dat;
}

static long query_(SegTree[] tree, int rt, int l, int r) {
if (l <= tree[rt].start && r >= tree[rt].end) {
return tree[rt].dat;
}

int mid = tree[rt].start + tree[rt].end >> 1;
long ans = 0;
if (l <= mid) ans += query_ (tree, rt << 1, l, r);
if (r >= mid + 1) ans += query_ (tree, rt << 1 | 1, l, r);
return ans;
}
}



tsao
2019-09-26 06:44

1~n个点，m条边的有向图。无重边，无负环，每条边有两个属性，长度和花费的金币，求从1到n的花费不超过k的最短路。

tsao
2019-08-26 17:17

spfa

int INF = 0x3f3f3f3f;
res = dist[n] == INF ? -1 : dist[n];


Bellman-Ford 和 Floyd判断：

// Bellman-Ford
int INF = 0x3f3f3f3f;
int res = dist[n] > INF/2 ? -1 : dist[n];
// Floyd
int res = d[i][j] > INF /2 ? -1 : d[i][j];


tsao
2019-08-08 16:24