P8444 不等价交换法则-526互联

~~B题出题人好可爱！~~

一.题意概述

个人觉得题意很好理解。先用 w 元钱买一个物品。不是非得用 w 元钱，而是 w 元钱买得下就行。然后，用这一个物品去换别的物品，换得越多越好。最后输出能有多少个物品，当然如果你什么都换不起，就输出 1 ，代表原来买的那一个。如果一开始 w 元钱什么都买不起，恭喜喜提大零蛋。

二.正解

我觉得，其实钻题目空子没什么意思。所以一开始就没想过打暴力，我的方法是后缀和+二分。

Part 1

出现变量解释

#include<bits/stdc++.h>
using namespace std;
long long n;//商品数
int a[1000005];//价格
long long hz[1000005];//后缀和
long long w;//一开始有w元

bool cmp(int a,int b){//从大到小排序函数
	return a>b;
}

Part 2

输入解释

void init(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>w;
	sort(a+1,a+1+n,cmp);//对a数组从大到小排序
	for(int j=n;j>=1;j--){
		hz[j]=hz[j+1]+a[j];//后缀和计算
	}
}

Part 3

二分函数

long long erfen(int l,int r){ //前端点，后端点
	if(l==r) return a[l];
	int mid=(l+r)/2;
	if(a[mid]<=w){
		return erfen(l,mid);
	}
	else{
		return erfen(mid+1,r);
	}
}//二分板子

Part 4

输出

int main(){
	init();//输入函数
	long long val;//w能买的物品的最大价值
	if(w<a[n]) val=0;//最便宜的都买不起
	else val=erfen(1,n);
	int cnt;//答案
	for(int i=n;i>=1;i--){
		if(hz[i]>val){//根据后缀和从价值小换到价值大
			cnt=n-i;
			break;
		}
	}
	cout<<cnt;
	return 0;
}

Part 5

完整代码

#include<bits/stdc++.h>
using namespace std;
long long n;
int a[1000005];
long long hz[1000005];
long long w;

bool cmp(int a,int b){
	return a>b;
}

void init(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>w;
	sort(a+1,a+1+n,cmp);	
	for(int j=n;j>=1;j--){
		hz[j]=hz[j+1]+a[j];
	}
}

long long erfen(int l,int r){
	if(l==r) return a[l];
	int mid=(l+r)/2;
	if(a[mid]<=w){
		return erfen(l,mid);
	}
	else{
		return erfen(mid+1,r);
	}
}

int main(){
	init();
	long long val;
	if(w<a[n]) val=0;
	else val=erfen(1,n);
	int cnt;
	for(int i=n;i>=1;i--){
		if(hz[i]>val){
			cnt=n-i;
			break;
		}
	}
	cout<<cnt;
	return 0;
}

管理大大求过