上海计算机学会2024年1月月赛C++乙组T4最优顺序
发布时间
阅读量：
阅读量
最优顺序
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 对数字 (w1,s1),…,(wn,sn)，请为这些数对重新安排一个合理的顺序，使得最大的 ai 尽可能小，输出这个值。
ai 定义为 w1+w2+⋯+wi−1−si，也就是该数对前的所有 w 之和与本数对的 s 之差。
输入格式
- 第一行：单个整数 n
- 第二行到第 n+1 行：每行两个整数表示 wi 与 si
输出格式
- 单个整数：表示最大的 ai 的最小值。
数据范围
- 对于 30% 的数据，1≤n≤100，1≤wi,si≤100；
- 对于 60% 的数据，1≤n≤20,000，1≤wi,si≤10,000；
- 对于 100% 的数据，1≤n≤300,000，1≤wi,si≤10^9。
样例数据
输入:
3
10 1
5 5
1 8
输出:
5
说明:
重新安排的顺序应该是
1 8
5 5
10 1
解析：
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
struct node {
int w;
int s;
};
node a[300005];
//s的增加不足以抵消w减少时排在前边
bool cmp(node x,node y){
return x.s-y.s<y.w-x.w;
}
long long ans=-1e18;//默认最小值
int main() {
cin>>n;
int mx=0;
int k;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].s;
}
sort(a+1,a+n+1,cmp);//排序
long long sum=0;
for(int i=1;i<=n;i++){//模拟，求最大值
ans=max(ans,sum-a[i].s);
sum+=a[i].w;
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~