社区讨论

92pts,求条

P1956Sum参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mli80zsi
此快照首次捕获于
2026/02/12 00:05
4 周前
此快照最后确认于
2026/02/14 10:55
4 周前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
int const N = 1e5 + 7;
ll a[N], s[N];
int n;
ll k, p;

int main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

  cin >> n >> k >> p;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    s[i] = (s[i - 1] + a[i] % p) % p;
  }

  set<ll> st;
  st.insert(0); 
  ll ans = LLONG_MAX;

  for(int j = 1; j <= n; j++){
    ll target = s[j] - k;
    auto it = st.upper_bound(target);
    if(it != st.begin()){
      it--;
      ll val = (s[j] - *it + p) % p;
      if(val >= k) ans = min(ans, val);
    }

    if(!st.empty()){
      ll val = (s[j] - *st.begin() + p) % p;
      if(val >= k) ans = min(ans, val);
    }
    
    st.insert(s[j]);
  }

  cout << ans << "\n";
  return 0;
}


// author: Kasty

回复

1 条回复,欢迎继续交流。

正在加载回复...