打卡信奥刷题（2516）用C++实现信奥 P1956 Sum

P1956 Sum

题目描述

给出一个数列a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​和k,pk,pk,p；

设Si,j=∑k=ijakS_{i,j}=\sum\limits_{k=i}^ja_kSi,j​=k=i∑j​ak​，则：
Answer=min⁡{Si,j mod p ∣ Si,j mod p≥k}\mathit{Answer}=\min\{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}Answer=min{Si,j​modp∣Si,j​modp≥k}
其中，i≤j,{Si,j mod p ∣ Si,j mod p≥k}≠∅i\le j, \{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}\ne\varnothingi≤j,{Si,j​modp∣Si,j​modp≥k}=∅。

输入格式

第一行三个正整数n,k,pn,k,pn,k,p。

第二行nnn个正整数，表示a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​。

输出格式

一行一个正整数，表示Answer\mathit{Answer}Answer。

输入输出样例 #1

输入 #1

7 2 17 12 13 15 11 16 26 11

输出 #1

2

说明/提示

数据范围

对于100%100\%100%的数据，1≤n≤1051\le n\le10^51≤n≤105，1≤k,p,ai≤10181\le k,p,a_i\le10^{18}1≤k,p,ai​≤1018。

C++实现

#include<set>#include<stdio.h>#include<algorithm>#defineintlonglongusingstd::min;std::set<int>q;ints[100005];signedmain(){q.insert(0);intn,k,p,i,x,res=1ll<<60;scanf("%lld %lld %lld",&n,&k,&p);for(i=1;i<=n;++i){scanf("%lld",&x);s[i]=(s[i-1]+x)%p;}for(i=1;i<=n;++i){res=min(res,s[i]+(s[i]<k?p:0)-(*--q.upper_bound((s[i]+p-k)%p)));q.insert(s[i]);}printf("%lld",res);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容