2025.4.9拼多多笔试

1.找到s最长的连续1是否为9，这个直接双指针模拟即可。

void solve() {
  int mx = 0, n;
  cin >> n;

  string s;
  cin >> s;
  for (int i = 0; i < n; i++) {
    int j = i;
    while (j < n && s[j] == '1') {
      j++;
    }
    mx = max(mx, j - i);
    if (mx > 9) {
      break;
    }
  }
  if (mx == 9) {
    cout << "lucky\n";
  } else {
    cout << "unlucky\n";
  }
}

2.忘记题目意思了，思路是对于n-1个，我只拿(k+1)/2-1个，因为这些次数都是白嫖的，然后剩下的再看那个表达式求一下就行。

void solve() {
  ll n, m, K;
  cin >> n >> m >> K;

  ll k = (K + 1) / 2;
  ll r = m - (k - 1) * (n - 1);
  if (r <= 0) {
    cout << "0" << '\n';
  } else {
    cout << r / K + (r % K >= k) << '\n'; 
  }
}

3.不记得题目了，然后我暴力check写假了，但是100%了，说一下正确的思路，

首先n>m则答案一定是-1，n<m则sort一下从大到小输出，只需要讨论n=m的时候如何填写。

考虑贪心S的每个位置尽量取<=T的那个位置最大的能填的，为什么说是能填的，因为可能填完这个你还需要保证后续能正常填完。

因此我们考虑一个暴力的思路，记录一个small标记，表示前面是否S串严格小于T串了。

分情况讨论：

1）若small标记为true，则S当前位置不受T串影响了，可以直接从大的开始取

2）若small标记为false，则S串最大只能从T这个位置的数字开始，考虑当且仅当S这个位置取T这个位置相同的数字时，需要check，因为一旦small标记了，后面可以随便填都会严格小于T，所以我们只需要考虑当S这个位置和T取相同数字时，暴力向后优先填最小的，如果这种策略都不能填完的话，就代表当前位置不能取和T相同的数字。

可以发现这个算法的复杂度会被check决定，而在n=m，当所有n+m个数都是1时，复杂度就是O(n^2)显然不可通过。

因此思考一下算法瓶颈，check复杂度太搞了，能不能减少次数，又观察到答案的前面某一部分一定会和T串相同，那我们是不是可以直接二分出来这个相同的长度，这样就做到了O(nlogn),具体来说check只加了一点东西，满足S数组中的数比T前mid个位置的数每个数字多，对于后面的位置能不能填，直接暴力模拟每次填最小的数即可。

4.也不太记得题目了，思路是这个题目是个贪心题，我们考虑排序从小到大去考虑每个商品的价格，它能使用的优惠券一定是满足阈值比他小的，所以我们只要挑满足阈值比他小的券，且挑能减免度最大的那一张，这个可以通过priority_queue完成。

void solve() {
  int n, m;
  cin >> n >> m;

  vector<int> p(n);
  vector<pair<int, int>> a(m);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> a[i].first >> a[i].second;
  }

  priority_queue<pair<int, int>> pq;
  // a[i] <= p[i]
  sort(a.begin(), a.end());
  sort(p.begin(), p.end());
  ll ans = 0;
  for (int i = 0, j = 0; i < n; i++) {
    while (j < m && a[j].first <= p[i]) {
      pq.push({a[j].second, a[j].first});
      j++;
    }
    if (!pq.empty()) {
      ans += pq.top().first;
      pq.pop();
    }
  }
  cout << ans << '\n';
}