#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
int n,a[N];
LL c[N];
int main()
{
scanf("%d",&n);
LL avg=0;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),avg+=a[i];
avg/=n;
for(int i=1;i<=n;++i) c[i]=c[i-1]+avg-a[i];
sort(c+1,c+1+n);
LL res=0;
for(int i=1;i<=n;++i)
res+=abs(c[i]-c[(n+1)/2]);
printf("%lld",res);
return 0;
}
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef pair<double,double> PDD;
#define l first
#define r second
const int N=1010;
int n;
PDD seg[N];
double d;
int main()
{
cin>>n>>d;
bool f=true;
for(int i=0;i<n;++i)
{
int x,y;
cin>>x>>y;
if(y>d) f=false;
double len=sqrt(d*d-y*y);
seg[i]={x-len,x+len};
}
if(!f)
{
printf("-1");
return 0;
}
sort(seg,seg+n);
int res=0;
double ed=-1e18;
for(int i=0;i<n;++i)
if(ed+1e-6<seg[i].l)
{
++res;
ed=seg[i].r;
}
else ed=min(ed,seg[i].r);
printf("%d",res);
return 0;
}
二,
题1 1235. 付账问题
打卡
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long double LD;
const int N=500010;
int n,a[N];
int main()
{
LD s;
scanf("%d%Lf",&n,&s);
for(int i=0;i<n;++i) scanf("%d",&a[i]);
sort(a,a+n);
LD res=0,avg=s/n;
for(int i=0;i<n;++i)
{
LD cur=s/(n-i);
if(a[i]<cur) cur=a[i];
res+=(cur-avg)*(cur-avg);
s-=cur;
}
printf("%.4Lf",sqrt(res/n));
return 0;
}
题2 1239. 乘积最大
打卡
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100010,MOD=1000000009;
int n,k;
int a[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i) scanf("%d",&a[i]);
sort(a,a+n);
int res=1,l=0,r=n-1,sign=1;
if(k&1)
{
res=a[r--];
--k;
if(res<0) sign=-1;
}
while(k)
{
LL x=(LL)a[l]*a[l+1],y=(LL)a[r-1]*a[r];
if(x*sign>y*sign)
{
res=x%MOD*res%MOD;
l+=2;
}
else
{
res=y%MOD*res%MOD;
r-=2;
}
k-=2;
}
printf("%d",res);
return 0;
}
题3 1247. 后缀表达式
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=200010;
int n,m,k;
int a[N];
int main()
{
scanf("%d%d",&n,&m);
k=n+m+1;
for(int i=0;i<k;++i) scanf("%d",&a[i]);
LL res=0;
if(!m)
for(int i=0;i<k;++i) res+=a[i];
else
{
sort(a,a+k);
res=a[k-1]-a[0];
for(int i=1;i<k-1;++i) res+=abs(a[i]);
}
printf("%lld",res);
return 0;
}
题4 1248. 灵能传输
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=300010;
int n;
LL a[N],s[N];
bool st[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld",a+i),s[i]=s[i-1]+a[i];
LL s0=s[0],sn=s[n];
if(s0>sn) swap(s0,sn);
sort(s,s+n+1);
for(int i=0;i<=n;++i)
if(s[i]==s0)
{
s0=i;
break;
}
for(int i=n;i>=0;--i)
if(s[i]==sn)
{
sn=i;
break;
}
memset(st,0,sizeof st);
int l=0,r=n;
for(int i=s0;i>=0;i-=2)
{
a[l++]=s[i];
st[i]=true;
}
for(int i=sn;i<=n;i+=2)
{
a[r--]=s[i];
st[i]=true;
}
for(int i=0;i<=n;++i)
if(!st[i]) a[l++]=s[i];
LL res=0;
for(int i=1;i<=n;++i)
res=max(res,abs(a[i]-a[i-1]));
printf("%lld\n",res);
}
return 0;
}