#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int n,m;
int g[N];
int jdz(int x)
{
if(x>=0)
return x;
return -x;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int r=m/(n+1);
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=a[i-1];j<a[i];j++)
{
int x=jdz(i-1-j/r);
res+=x;
}
}
for(int i=a[n];i<m;i++)
{
int x=jdz(n-i/r);
res+=x;
}
cout<<res;
return 0;
}
活动打卡代码
AcWing 4281. 序列查询新解
题目描述
blablabla
样例
blablabla
算法1
现在第一题也得想一下了
C++ 代码
#include<iostream>
using namespace std;
const int N=210;
int a[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int res=0; //记录答案
int s=0; //s记录上一个a[i];
for(int i=1;i<=n;i++)
{
res+=(i-1)*(a[i]-s); a[i]到a[i-1]之间的预算都只能推荐a[i-1]这件商品
s=a[i];
}
if(m>a[n])// m一定大于a[n],这里if可以省略
res+=n*(m-a[n]); //预算超过的另外算
cout<<res;
return 0;
}
活动打卡代码
AcWing 4280. 序列查询
#include<iostream>
using namespace std;
const int N=210;
int a[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int res=0;
int s=0;
for(int i=1;i<=n;i++)
{
res+=(i-1)*(a[i]-s);
s=a[i];
}
if(m>a[n])
res+=n*(m-a[n]);
cout<<res;
return 0;
}
活动打卡代码
AcWing 4007. 非零段划分
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N=500003,M=10004;
int a[N],n,cnt[M];
int main()
{
scanf(“%d”,&n);
for(int i=1;i<=n;i++)
scanf(“%d”,&a[i]);
n=unique(a+1,a+1+n)-a-1;
a[0]=a[n+1]=0;
for (int i = 1; i <= n; i ++ )
{
int x = a[i - 1], y = a[i], z = a[i + 1];
if (x < y && z < y) cnt[y] ++ ;
else if (x > y && z > y) cnt[y] -- ;
}
int res=0,sum=0;
for(int i=M-1;i;i--)
{
sum+=cnt[i];
res=max(res,sum);
}
cout<<res;
return 0;
}
```
活动打卡代码
AcWing 3411. 灰度直方图
#include<iostream>
using namespace std;
const int N=510;
int g[N][N];
int n,m,l;
int h[256];
int main()
{
cin>>n>>m>>l;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
h[g[i][j]]++;
for(int i=0;i<l;i++)
{
cout<<h[i]<<' ';
}
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 4006. 数组推导
#include<iostream>
using namespace std;
const int N=110;
int n;
int b[N];
int main()
{
cin>>n;
int sum=0;
for(int i=1;i<=n;i++)
{
cin>>b[i];
sum+=b[i];
}
cout<<sum<<endl;
int a=-1;
for(int i=1;i<=n;i++)
{
if(b[i]>a)
a=b[i];
else
sum-=b[i];
}
cout<<sum;
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 5. 多重背包问题 II
#include<iostream>
using namespace std;
const int N=25000,M=2010;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s)
{
cnt++;
v[cnt]=k*a;
w[cnt]=k*b;
s-=k;
k*=2;
}
if(s>0)
{
cnt++;
v[cnt]=s*a;
w[cnt]=s*b;
}
}
for(int i=1;i<=cnt;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
include[HTML_REMOVED]
using namespace std;
const int N=25;
int a[N],b[N],c[N],h[N];
int n,m;
int main()
{
c[0]=1;
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i)
{
scanf(“%d”,&a[i]);
c[i]=c[i-1]*a[i];
h[i]=m%c[i];
}
for(int i=1;i<=n;i)
{
b[i]=(h[i]-h[i-1])/c[i-1];
}
for(int i=1;i<=n;i++)
cout<<b[i]<<’ ‘;
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
活动打卡代码
AcWing 4699. 如此编码
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
include[HTML_REMOVED]
using namespace std;
const int N=25;
int a[N],b[N],c[N],h[N];
int n,m;
int main()
{
c[0]=1;
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i)
{
scanf(“%d”,&a[i]);
c[i]=c[i-1]*a[i];
h[i]=m%c[i];
}
for(int i=1;i<=n;i)
{
b[i]=(h[i]-h[i-1])/c[i-1];
}
for(int i=1;i<=n;i++)
cout<<b[i]<<’ ‘;
return 0;
}
活动打卡代码
AcWing 4956. 冶炼金属
//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n ; cin >> n ;
int mi = 0 , mx = 2e9 ;
for(int i = 1 ; i <= n ; i ++)
{
int a , b ; cin >> a >> b ;
int r = a/b , l = a/(b+1)+1;
mi = max(mi , l) , mx = min(mx , r) ;
}
cout << mi << ' ' << mx << endl ;
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
