题目地址
题解
贪心。
按照产奶时间从大到小排序，然后小的和大的配对，更新最长时间即可。
这不是普及组原题么
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#define INF 2000000000
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int (){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
P p[100005];
int n,ans=0;
void init(){
n=read();
for(int i=1;i<=n;i++)p[i].second=read(),p[i].first=read();
sort(p+1,p+1+n);
}
void solve(){
int po=n;
for(int i=1;i<=n;i++){
while(po>i&&p[i].second>=p[po].second){
if(p[po].second)
p[i].second-=p[po].second,ans=max(ans,p[i].first+p[po].first);
po--;
}
if(po==i)break;
p[po].second-=p[i].second;
}
printf("%dn",ans);
}
int main(){
init();
solve();
return 0;
}
|
近期评论