题解:贪心
#include
using namespace std;
typedef long long LL;
typedef pair<int ,int > PII;
const int N=1e5+10;
int n;
int a[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
LL sum=0;
for(int i=1;i<n;i++){
if(a[i]>a[i-1]) sum+=a[i]-a[i-1];
}
printf("%lld",sum);
return 0;
}
题目:104. 货仓选址
题解:贪心,选中位数即可
#include
using namespace std;
typedef long long LL;
typedef pair<int ,int > PII;
const int N=1e5+10;
int n;
int a[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int t=(n+1)/2;
LL sum=0;
for(int i=1;i<=n;i++){
sum+=abs(a[t]-a[i]);
}
printf("%lld",sum);
return 0;
}
题目:122. 糖果传递
题解:中位数+贪心+数学推导
#include
using namespace std;
typedef long long LL;
typedef pair<int ,int > PII;
const int N=1e6+10;
int n;
LL a[N];
int main(){
cin>>n;
LL sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
sum/=n;
for(int i=1;i<=n;i++){
a[i]=sum-a[i];
a[i]+=a[i-1];
}
sort(a+1,a+1+n);
LL ans=0;
for(int i=1;i<=n;i++){
ans+=abs(a[i]-a[(n+1)/2]);
}
printf("%lld",ans);
return 0;
}
题目:112. 雷达设备
题解:贪心+数学
#include
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=1e6+10;
int n,d;
PII a[1010];
int main(){
cin>>n>>d;
int x,y;
bool flag=1;
for(int i=0;i<n;i++){
scanf("%d%d",&x,&y);
a[i].first=x+sqrt((double)d*d-y*y);
a[i].second=x-sqrt((double)d*d-y*y);
if(y>d) flag=0;
}
if(!flag){
puts("-1");
}else{
sort(a,a+n);
double r=-2000;
int ans=0;
for(int i=0;i<n;i++){
if(r<a[i].second){
ans++;
r=a[i].first;
}
}
printf("%d",ans);
}
return 0;
}
题目:1235. 付账问题
题解:贪心+均值不等式
#include
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=5e5+10;
LL n,s;
int a[N];
int main(){
cin>>n>>s;
double AVG=s*1.0/n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
double avg=AVG,x=0;
for(int i=1;i<=n;i++){
if(a[i]<avg){
s-=a[i];
x+=(a[i]-AVG)*(a[i]-AVG);
avg=s*1.0/(n-i);
}else{
s=0;
x+=(avg-AVG)*(avg-AVG)*(n-i+1);
break;
}
}
x/=n;
x=sqrt(x);
printf("%.4f",x);
return 0;
}
题目:1239. 乘积最大
题解:附上大佬解题思路
上图来源
#include
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=1e5+10;
const int mod=1000000009;
int n,k;
LL a[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+1+n);
LL sum=1;
int sign=1;
if(k%2){
sum=(sum*a[n])%mod;
if(a[n]<0) sign=-1;
n--;
k--;
}
int i=1,j=n;
while(k){
if(sign*a[i]*a[i+1]>sign*a[j]*a[j-1]){
sum=((sum*a[i])%mod*a[i+1])%mod;
i+=2;
}else{
sum=((sum*a[j])%mod*a[j-1])%mod;
j-=2;
}
k-=2;
}
printf("%lld",sum);
return 0;
}
题目:1247. 后缀表达式
题解:如果没有负号就是全部相加,如果有负号,就是加上最大的数,然后减去最小的数,中间剩余的都加上其绝对值
#include
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=2e5+10;
const int mod=1000000009;
int n,m;
int a[N];
int main(){
cin>>n>>m;
for(int i=0;i<n+m+1;i++)
scanf("%d",&a[i]);
sort(a,a+n+m+1);
if(m==0){
LL sum=0;
for(int i=0;i<n+m+1;i++){
sum+=a[i];
}
printf("%lld",sum);
}else{
LL sum=0-a[0]+a[n+m];
for(int i=1;i<n+m;i++){
sum+=abs(a[i]);
}
printf("%lld",sum);
}
return 0;
}
题目:1248. 灵能传输
题解:大佬题解
#include
using namespace std;
typedef long long LL;
typedef pair<int ,int >PII;
const int N=3e5+10;
int t;
int n;
LL s[N],a[N];
int main() {
cin>>t;
while(t--){
cin>>n;
s[0]=0;
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
LL s0=0,sn=s[n];
if(s0>sn){
swap(s0,sn);
}
sort(s,s+n+1);
for(int i=0;i<=n;i++){
if(s0==s[i]){
s0=i;
break;
}
}
for(int i=n;i>=0;i--){
if(sn==s[i]){
sn=i;
break;
}
}
bool sta[N];
memset(sta,0,sizeof sta);
int l=0,r=n;
for(int i=s0;i>=0;i-=2){
a[l++]=s[i];
sta[i]=1;
}
for(int i=sn;i<=n;i+=2){
a[r--]=s[i];
sta[i]=1;
}
for(int i=0;i<=n;i++){
if(!sta[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;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)