---------------------------------------------------------------------------------------------------------------------------------
题目描述
有M(M为偶数)头奶牛,每头奶牛有一个产奶量,将这些奶牛两两配对,每对奶牛的产奶的时间为两头奶牛产奶量的总和。现在这M/2对奶牛同时产奶,问所需的最短时间是多少 M保证为偶数
第一行为一个正整数N
接下来有N行,每行两个正整数x和y,表示有x头奶牛的产奶量为y。保证所有x的总和等于M
【输出格式】
输出产奶时间的最小值
【输入输出样例#1】
输入#1
3
1 8
2 5
1 2
输出#1
10
【说明提示】
奶牛的产奶量分别为8,5,5,2。
让8和2配对,5和5配对,则产奶时间分别为10,10,所以这两对奶牛同时产奶的时间为10.
---------------------------------------------------------------------------------------------------------------------------------
这道题我先翻译了一下题意,他是想让我们把这些奶牛两两配对,让最大和最小,所以让第yi'ge一配倒数第一,第二配倒数第二就行了。
然后我先是用一个vector把所有产奶量记下来,如样例我会输入成8,5,5,2。但是因为m的范围是10^9,所以要直接往vector里装struct。
结果,我的做法超时了,我爸爸说这是因为我是一个一个算最大值的,但这样算的东西一直一样,相当于白算了。所以,我又改成了一段一段算,就全部AC了。
---------------------------------------------------------------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x,y;
};
vector<node>v;
bool cmp(node n1,node n2)
{
return n1.y<n2.y;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
node op;
cin>>op.x>>op.y;
v.push_back(op);
}
int m=v.size();
sort(v.begin(),v.end(),cmp);
int maxx=0;
int l=0,r=m-1;
while(l<=r)
{
int sum=v[l].y+v[r].y;
int minn=min(v[l].x,v[r].x);
v[l].x-=minn;
v[r].x-=minn;
if(v[l].x<=0)
l++;
if(v[r].x<=0)
r--;
maxx=max(maxx,sum);
}
cout<<maxx;
return 0;
}