【LeetCode第79场双周赛】

模拟

class Solution {
public:
    bool digitCount(string num) {
        vector cnt(10, 0);
        for(int i = 0; i < num.size(); ++i)
            cnt[num[i] - '0'] += 1;
        for(int i = 0; i < num.size(); ++i)
            if(cnt[i] != num[i] - '0') return false;
        return true;
    }
};

排序去重、比大小

class Solution {
public:
    string largestWordCount(vector& messages, vector& senders) {
        struct Node {
            string name;
            int cnt;
        };
        
        vector vec; 
        for(int i = 0; i < senders.size(); ++i) {
            int c = 0;
            for(auto u : messages[i]) 
                if(u == ' ') c += 1;
            vec.push_back({senders[i], c + 1});
        }
        sort(vec.begin(), vec.end(), [](const Node& A, const Node &B) {
            return A.name > B.name; 
        });
        
        string name = vec[0].name;
        int sum = 0;
        int n = vec.size();
        for(int i = 0; i < n; ++i) {
            int j = i;
            int temp = 0;
            while(j < n && vec[j].name == vec[i].name) temp += vec[j].cnt, j += 1;
            if(temp > sum) sum = temp, name = vec[i].name;
            i = j - 1;
        } 
        
        return name;
    }
};

度数越大赋值越大

class Solution {
public:
    long long maximumImportance(int n, vector>& roads) {
        vector d(n, 0);
        for(auto u : roads) d[u[0]] += 1, d[u[1]] += 1;
        sort(d.begin(), d.end(), greater());
        
        long long res = 0;
        for(int i = 0, j = n; i < n; ++i, --j) {
            res += 1ll * j * d[i];
        }
        return res;
    }
};

线段树好题！
根据题目题意，每行只有前缀座位会被占座，不会出现中间被占座的情况。
本题的难点在于，当进行gather时，需要找到大于等于 k k k 的最小row。
这里的思想在于优先判断左区间，如果左区间不合法再处理右区间，这就是在线段树上进行二分。
此外，由于每个row只会用尽一次，因此我们动态更新可以使用的最小row。

#include
using namespace std;

typedef long long ll;

const int N = 50010;
typedef long long ll;
struct Node {
    int l, r;
    int last;
    ll sum;
}tr[N << 2];
int a[N];
int n, m, st;

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].last = max(tr[u << 1].last, tr[u << 1 | 1].last);
}

void build(int u, int l, int r) {
    tr[u] = {l, r, m, m};
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

int query_index(int u, int x) {
    if(tr[u].l == tr[u].r) {
        if(tr[u].last >= x) return tr[u].l;
        else return 0;
    }
    if(tr[u << 1].last >= x) return query_index(u << 1, x);
    else if(tr[u << 1 | 1].last >= x) return query_index(u << 1 | 1, x);
    else return 0;
}

int query_sum(int u, int k) {
    if(tr[u].l == tr[u].r) {
        return tr[u].l;
    }

    if(tr[u << 1].sum >= k) return query_sum(u << 1, k);
    else return query_sum(u << 1 | 1, k - tr[u << 1].sum);
}

void modify(int u, int p, int x) {
    if(tr[u].l == p && tr[u].r == p) {
        tr[u].sum -= x;
        tr[u].last -= x;
        a[p] += x;
        return ;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if(p <= mid) modify(u << 1, p, x);
    else modify(u << 1 | 1, p, x);
    pushup(u);
}

class BookMyShow {
public:

    BookMyShow(int _n, int _m) {
        n = _n, m = _m;
        for(int i = 1; i <= n; ++i) a[i] = 0;
        build(1, 1, n);
        st = 1;
    }
    
    vector gather(int k, int maxRow) {
        maxRow += 1;
        
        if(st > maxRow) return {};
        
        // 找到 >= k 的最小索引
        int idx = query_index(1, k);
        if(idx == 0 || idx > maxRow) return {};
        
        vector ans = {idx - 1, a[idx]};
        modify(1, idx, k);
        
        while(st <= n && a[st] == m) st += 1;
        
        return ans;
    }
    
    bool scatter(int k, int maxRow) {
        maxRow += 1;
        
        if(tr[1].sum < k) return false;
        int idx = query_sum(1, k);
        if(idx > maxRow) return false;
        
        for(int i = st; i <= idx; ++i) {
        	int temp = min(k, m - a[i]);
            modify(1, i, temp);
            k -= temp;
        }
        
        while(st <= n && a[st] == m) st += 1;
        
        return true;
    }
};