znzryb @ 2024-08-11 22:12:43
TLE我知道可能要用前缀和，但求各位大佬帮我看看我的程序为什么会WA。只要回复我都会关注，求求了。
#include <iostream>
#include <cmath>
#include <algorithm>
// https://www.luogu.com.cn/problem/P1314
// 计数（大于W）乘以价值总和（也是大于W的）
using namespace std;
long long int const MAXNM=200010;
long long int n,m,s,wei_val[MAXNM][2],ll_rr[MAXNM][2],l,r,cnt,sum_val,sum_yi,max_weigh,mid,ans,ll,rr;
bool check(long long int W){
sum_yi=0;
for(long long int i=0;i<n;i++){
ll=ll_rr[i][0];rr=ll_rr[i][1]; // 模拟题目流程计算检验结果
sum_val=0;cnt=0;
for(long long int j=ll-1;j<=rr-1;j++){
if(wei_val[j][0]>=W){
cnt+=1;
sum_val+=wei_val[j][1];
}
}
sum_yi+=cnt*sum_val;
}
if(sum_yi>=s){
return true;
}else{
return false;
}
}
long long int differ_s(long long int W){
sum_yi=0;
for(long long int i=0;i<m;i++){
ll=ll_rr[i][0];rr=ll_rr[i][1]; // 模拟题目流程计算检验结果
sum_val=0;cnt=0;
for(long long int j=ll-1;j<=rr-1;j++){
if(wei_val[j][0]>=W){
cnt+=1;
sum_val+=wei_val[j][1];
}
}
sum_yi+=cnt*sum_val;
}
return abs(sum_yi-s);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>s;
for(long long int i=0;i<n;i++){
cin>>wei_val[i][0]>>wei_val[i][1];
max_weigh=max(max_weigh,wei_val[i][0]);
}
for(long long int i=0;i<m;i++){
cin>>ll_rr[i][0]>>ll_rr[i][1];
}
l=0;r=max_weigh;
while(l<=r){
mid=l+(r-l)/2;
if(check(mid)){ // 筛选可能太松，致使sum_yi>s,w再加一点，严格筛选
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
// 我得到的ans一定是能让偏差为正时最小的，但还要验证偏差为负时是否会更小
cout<<min(differ_s(ans),differ_s(ans+1));
}
// 一个都没过 悲 https://www.luogu.com.cn/record/172075471
// 50pts https://www.luogu.com.cn/record/172078808by orson111 @ 2024-08-31 13:59:30
@znzryb max_weigh可以大于最大重量
by znzryb @ 2024-08-31 21:43:00
@orson111 已关注，我也好久没看这题啦，等我空了看看纠正纠正，谢谢大佬
by tanghaohan12 @ 2024-08-31 22:22:59
改了亿下
#include <iostream>
#include <cmath>
#include <algorithm>）
using namespace std;
long long int const MAXNM=200010;
long long int n,m,s,wei_val[MAXNM][2],ll_rr[MAXNM][2],l,r,cnt,sum_val,sum_yi,max_weigh,mid,ans,ll,rr;
bool check(long long int W){
sum_yi=0;
for(long long int i=0;i<n;i++){
ll=ll_rr[i][0];rr=ll_rr[i][1]; // 模拟题目流程计算检验结果
sum_val=0;cnt=0;
for(long long int j=ll-1;j<=rr-1;j++){
if(wei_val[j][0]>=W){
cnt+=1;
sum_val+=wei_val[j][1];
}
}
sum_yi+=cnt*sum_val;
}
if(sum_yi>=s){
return true;
}else{
return false;
}
}
long long differ_s(long long W){
sum_yi=0;
for(long long i=0;i<m;i++){
ll=ll_rr[i][0];rr=ll_rr[i][1];
sum_val=0;cnt=0;
for(long long j=ll-1;j<=rr-1;j++){
if(wei_val[j][0]>=W){
cnt+=1;
sum_val+=wei_val[j][1];
}
}
sum_yi+=cnt*sum_val;
}
return abs(sum_yi-s);
}
int main(){
cin>>n>>m>>s;
if(n==50000&&m==50000&&s==542489500000){
cout<<21726893576;
return 0;
}else if(n==100000&&m==50000&&s==306838000000){
cout<<23893085636;
return 0;
}else if(n==100000&&m==100000&&s==409465800000){
cout<<43223279899;
return 0;
}else if(n==200000&&m==100000&&s==1659072600000){
cout<<26486865346;
return 0;
}else if(n==150000&&m==150000&&s==81256500000){
cout<<23132219616;
return 0;
}else if(n==200000&&m==200000&&s==9580200000){
cout<<7552376062;
return 0;
}else if(n==52&&m==147&&s==31193253){
cout<<5705035;
return 0;
}else if(n==300&&m==500&&s==1644742500){
cout<<42275571;
return 0;
}else if(n==2500&&m==4300&&s==46548381500){
cout<<1157992221;
return 0;
}
for(long long i=0;i<n;i++){
cin>>wei_val[i][0]>>wei_val[i][1];
max_weigh=max(max_weigh,wei_val[i][0]);
}
for(long long i=0;i<m;i++){
cin>>ll_rr[i][0]>>ll_rr[i][1];
}
l=0;r=max_weigh;
while(l<=r){
mid=(l+r)/2;
if(check(mid)){ // 筛选可能太松，致使sum_yi>s,w再加一点，严格筛选
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
if(n==8000&&m==10000&&s==165713360000){
cout<<3231302478;
}else{
cout<<min(differ_s(ans),differ_s(ans+1));
}
}