C++14(g++5.4) 解法, 执行用时: 633ms, 内存消耗: 5224K, 提交时间: 2018-07-21 10:14:57

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Info{ll v,d,we;}a[6000010],b[6000010];
ll m,n,v,sum;
bool c1(const Info &a,const Info &b){return a.d<b.d;}
bool comp(const Info &a,const Info &b){if (a.v!=b.v)return a.v<b.v;return a.d<b.d;}
ll ans(ll x){
    if (m%2==0) return (b[x].v+b[x-1].v)/2;
    return b[x].v;
}
bool pan(ll mid){
    ll da=m/2,xi=m/2,ans=0;
    if (m%2==1){da++;}
    for (int i=1;i<=n;i++){
        if (a[i].we<mid){if (xi!=0){xi--;ans+=a[i].d;}}
        else{if (da!=0){da--;ans+=a[i].d;}}
        if (ans>v) return false;
    }
    if (da!=0||xi!=0) return false;
    return true;
}
int main(){
    srand(19217);
    cin>>v>>n>>m;
    for (int i=1;i<=n;i++)scanf("%d %d",&a[i].v,&a[i].d);
    sort(a+1,a+n+1,comp);
    for (int i=1;i<=n;i++){a[i].we=i;b[i]=a[i];}
    sort(a+1,a+n+1,c1);
    ll l=1+(m/2),r=n-(m/2),mid;
    if (m%2==0) r++;
    while (sum<=1e8/n){
        ll x=l+rand()%(r-l+1);
        if (pan(x))l=x;
        sum++;
    }
    cout<<ans(l)<<endl;
    return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 1442ms, 内存消耗: 42196K, 提交时间: 2020-06-24 23:24:48

#!/usr/bin/env python3
#
# 背包
#
import sys, os, heapq

def read_ints(): return list(map(int, input().split()))

v, n, m = read_ints()
a = sorted([read_ints() for _ in range(n)])
c, o = m // 2, m % 2

s1, s2 = [0] * n, [0] * n
h = []
for i in range(n):
	s1[i] = s1[i - 1] + a[i][1] if i > 0 else a[i][1]
	heapq.heappush(h, -a[i][1])
	if len(h) > c - (o ^ 1): s1[i] += heapq.heappop(h)
h = []
for i in range(n - 1, -1, -1):
	s2[i] = s2[i + 1] + a[i][1] if i < n - 1 else a[i][1]
	heapq.heappush(h, -a[i][1])
	if len(h) > c: s2[i] += heapq.heappop(h)

# print(a); print(s1, s2)

ans = 0
if m % 2 == 1:
	for i in range(n - c - 1, c - 1, -1):
		if a[i][1] + s1[i - 1] + s2[i + 1] <= v:
			ans = a[i][0]
			break
else:
	for i in range(c - 1, n - c):
		l = i + 1; r = n - c + 1
		while l < r:
			mi = (l + r) >> 1
			if s1[i - 1] + a[i][1] + s2[mi] <= v: l = mi + 1
			else: r = mi
		if l > i + 1:
			ans = max(ans, a[i][0] + a[l - 1][0])
	ans //= 2

print(ans)

C++11(clang++ 3.9) 解法, 执行用时: 46ms, 内存消耗: 2860K, 提交时间: 2020-07-08 12:59:10

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int a,b;
}R[100005];
bool cmp(node x,node y)
{	
	return x.a<y.a;
}
priority_queue<int>Q;
long long S1[100005]={0},S2[100005]={0};
int main()
{
    int i,w,n,m,l,r,mid,t,ans=0;
	scanf("%d%d%d",&w,&n,&m);
    for(i=1;i<=n;i++)scanf("%d%d",&R[i].a,&R[i].b);
    sort(R+1,R+1+n,cmp);
    for(i=1;i<=n;i++)
    {
    	Q.push(R[i].b),S1[i]=S1[i-1]+R[i].b;
    	if(i>m/2-1+m%2)S1[i]-=Q.top(),Q.pop();
	}
	while(!Q.empty())Q.pop();
	for(i=n;i>=1;i--)
	{
		Q.push(R[i].b),S2[i]=S2[i+1]+R[i].b;
		if(n-i+1>m/2)S2[i]-=Q.top(),Q.pop();
	}
	if(m&1)
	{
		for(i=n-m/2;i>m/2;i--)if(S1[i-1]+S2[i+1]+R[i].b<=w)break;
		ans=R[i].a;
	}
	else
	{
		for(i=m/2;i<=n-m/2;i++)
		{
			for(t=0,l=i+1,r=n-m/2+1;l<=r;)
			{
				mid=(l+r)>>1;
				if(S1[i-1]+S2[mid]+R[i].b<=w)t=mid,l=mid+1;
				else r=mid-1;
			}
			if(t)ans=max(ans,(R[i].a+R[t].a)/2);
		}
	}
	printf("%d\n",ans);
    return 0;
}