求助找不同
  • 板块题目总版
  • 楼主离落堕殇
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/9/30 22:45
  • 上次更新2023/11/4 05:17:11
查看原帖
求助找不同
399394
离落堕殇楼主2021/9/30 22:45

大佬们写题累了可以帮我看看这两份代码有什么区别么,一个100一个20


100分

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 2000010
#define int long long
using namespace std;
int n,m,r=0,l=214748364,mid,ans=999999999999999,s,sum,w[maxn],v[maxn],rt[maxn],lf[maxn],pv[maxn],pn[maxn];
inline bool ck(int x){
	memset(pv,0,sizeof(pv));
	memset(pn,0,sizeof(pn));
	for(int i=1;i<=n;i++)
		if(w[i]>=x){
			pv[i]=pv[i-1]+v[i];
			pn[i]=pn[i-1]+1;
		}
		else{
			pv[i]=pv[i-1];
			pn[i]=pn[i-1];
		}
	int y=0;
	for(int i=1;i<=m;i++)
		y+=(pn[rt[i]]-pn[lf[i]-1])*(pv[rt[i]]-pv[lf[i]-1]);
	sum=abs(y-s);
	if(y>s)	return 1;
	return 0;
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]),r=max(r,w[i]),l=min(l,w[i]);
	for(int i=1;i<=m;i++) scanf("%lld%lld",&lf[i],&rt[i]);
	l-=1,r+=2;
	while(l<=r){
		mid=(l+r)>>1;
		if(ck(mid)) l=mid+1;
		else r=mid-1;
		ans=min(ans,sum);
	}
	ans=min(ans,sum);
	printf("%lld",ans);
	return 0;
}

20分

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
long long n, m, s, ans=0x3f3f3f3f3f3f3f3f, vac=0;
long long l0=0x3f3f3f3f3f3f3f3f, r0=0, mid;
long long v[N], w[N], fv[N], fn[N], lf[N], ri[N];
bool check(int x){
	memset(fv, 0, sizeof(fv));
	memset(fn, 0, sizeof(fn));
	for(int i=1; i<=n; i++)
		if(w[i]>=x){
			fv[i]=fv[i-1]+v[i];
			fn[i]=fn[i-1]+1;
		}
		else{
			fv[i]=fv[i-1];
			fn[i]=fn[i-1];
		}
	int fa=0;
	for(int i=1; i<=m; i++) fa+=(fn[ri[i]]-fn[lf[i]-1])*(fv[ri[i]]-fv[lf[i]-1]);
	vac=abs(s-fa);
	if(fa>s) return true;
	return false;
}
int main(){ 
	scanf("%lld%lld%lld", &n, &m, &s);
	for(int i=1; i<=n; i++) {scanf("%lld%lld", &w[i], &v[i]); r0=max(r0, w[i]); l0=min(l0, w[i]);}
	for(int i=1; i<=m; i++) {scanf("%lld%lld", &lf[i], &ri[i]);}
	l0-=1; r0+=2;
	while(l0<=r0){
		mid=(l0+r0)>>1;
		if(check(mid)) l0=mid+1;
		else r0=mid-1;
		ans=min(ans, vac);
	}
	ans=min(ans, vac);
	printf("%lld", ans);
	return 0;
}

找了一个多小时了,求找不同大神指点

2021/9/30 22:45
加载中...