错题报告
得分情况
T1:100/100
T2:100/100
T3:100/100
T4:0/100
T5:100/100
T6:0/100
T4
正确代码:
#include <iostream>
#include <algorithm>
using namespace std;
#define N 50001
typedef pair < int , int > PII;
int n;
PII Q[N];
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
int w , s;
cin >> w >> s;
Q[i] = { w + s , w };
}
sort(Q + 1,Q + 1 + n);
int ans = -0x3f3f3f3f,sum = 0;
for (int i = 1; i <= n; i++){
int s = Q[i].first - Q[i].second;
ans = max(ans , sum - s);
sum += Q[i].second;
}
cout << ans;
return 0;
}
分析:按重量值和强壮值从小到大排序即为最优解。
T6
正确代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,m;
int d[N],s[N],t[N];
int cnt[N];
ll ccnt[N];
bool check(int x){
for(int i=1;i<=n;i++) ccnt[i]=cnt[i]-cnt[i-1];
for(int i=1;i<=x;i++){
ccnt[s[i]]-=d[i];
ccnt[t[i]+1]+=d[i];
}
for(int i=1;i<=n;i++){
ccnt[i]+=ccnt[i-1];
if(ccnt[i]<0) return true;
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&cnt[i]);
for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&s[i],&t[i]);
if(!check(m)){
printf("0");
return 0;
}
int l=1,r=m,ans=m+10;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) ans=min(ans,mid),r=mid-1;
else l=mid+1;
}
printf("-1\n%d",ans);
return 0;
}
分析:假设第i个位置无法满足订单要求,则后面的订单一定不满足要求,具有二段性,可以使用二分查找这个点。