C. Permute Digits dfs大模拟

http://codeforces.com/contest/915/problem/C

这题麻烦在前导0可以直接删除，比如

1001

100

应该输出11就好

我的做法是用dfs，每一位每一位的比较。在dfs的时候用一个char *指针指着b需要比较的位置，这样做方便很多。

2018年1月20日 16:35:51

身体好差，代码也很多不会写了。退役得真快。

 

bigger需要在新的一行里面弄，因为函数传参的时候不确定是哪个先，哪个后的。再正规点，不要一行写两次，带有++， --的东西

也就是不要

dfs(cmp, ++cmp)类似这样的

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
char str[33], sub[33];
int vis[222];
int lenstr, lensub;
bool flag;
int cut;
vector<int> vc;
bool dfs(int cur, bool bigger, char *cmp) {
    if (cur == min(lenstr - cut, lensub)) {
        if (lenstr - cut > lensub) return false;
        return true;
    }
    if (bigger) {
        for (int i = 9; i >= 0; --i) {
            if (!vis[i]) continue;
            vis[i]--;
            if (dfs(cur + 1, bigger, ++cmp)) {
                vc.push_back(i);
                return true;
            }
            vis[i]++;
        }
    } else {
        for (int i = (*cmp) - '0'; i >= 1; --i) {
            if (!vis[i]) continue;
            vis[i]--;
            bool t = bigger | (i < (*cmp) - '0');
            char *nex = cmp + 1;
            if (dfs(cur + 1, t, nex)) {
                vc.push_back(i);
                return true;
            }
            vis[i]++;
        }
    }
    if (!vis[0]) return false;
    if (cur != 0) {
        vis[0]--;
        bigger |= (*cmp) > '0'; //这里需要新的一行
        if (dfs(cur + 1, bigger, ++cmp)) {
            vc.push_back(0);
            return true;
        }
        vis[0]++;
        return false;
    } else {
        if (lenstr - cut -  1 < lensub) {
            vis[0]--;
            cut++;
            if (dfs(0, true, sub)) {
                return true;
            }
            vis[0]++;
            cut--;
        } else {
            vis[0]--;
            cut++;
            if (dfs(0, bigger, sub)) {
                return true;
            }
            vis[0]++;
            cut--;
        }
    }
    return false;
}
void work() {
    LL a, b;
    cin >> a >> b;
    sprintf(str, "%lld", a);
    sprintf(sub, "%lld", b);
    if (a == b) {
        printf("%lld\n", a);
        return;
    }
    lenstr = strlen(str), lensub = strlen(sub);
    if (lensub > lenstr) {
        for (int i = 0; i < lenstr; ++i) {
            int mx = -1, id = 0;
            for (int j = 0; j < lenstr; ++j) {
                if (vis[j]) continue;
                if (mx < str[j] - '0') {
                    mx = str[j] - '0';
                    id = j;
                }
            }
            vis[id] = true;
            printf("%d", mx);
        }
        return;
    }
    for (int i = 0; i < lenstr; ++i) vis[str[i] - '0']++;
    dfs(0, false, sub);
    for (int i = vc.size() - 1; i >= 0; --i) {
        printf("%d", vc[i]);
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

 

 

正解应该是一个贪心，经典的贪心

对于每一位，能否放x，条件是放了x后，能组成的最小的数不能大于b

 公司要求用go，学了几天用go写了一发

// _Channels_ are the pipes that connect concurrent
// goroutines. You can send values into channels from one
// goroutine and receive those values into another
// goroutine.

package main

import "fmt"
import (
    "bufio"
    "os"
)

// var (
//      mess make(chan string, 2)
// )

func main() {
    var str_a string
    var str_b int64
    input := bufio.NewReader(os.Stdin)
    fmt.Fscan(input, &str_a)
    fmt.Fscan(input, &str_b)
    var cnt [256]int
    for i := 0; i < len(str_a); i++ {
        cnt[str_a[i]-'0']++
    }
    var ans int64
    // fmt.Println(len(str_a))
    for i := 0; i < len(str_a); i++ {
        for j := 9; j >= 0; j-- {
            if cnt[j] == 0 {
                // fmt.Println(j, cnt[j])
                continue
            }
            flag := false
            t := ans
            t = t * 10
            t += int64(j)
            cnt[j]--

            if check(t, cnt, str_b) {
                ans = t
                flag = true
            } else {
                cnt[j]++
            }
            if flag {
                break
            }
        }
    }
    fmt.Println(ans)
}

func check(t int64, cnt [256]int, str_b int64) bool {
    for i := 0; i < 10; i++ {
        for cnt[i] > 0 {
            t = t * 10
            t += int64(i)
            cnt[i]--
        }
    }
    return t <= str_b
}