欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 3B Lorry

程序员文章站 2022-03-02 23:24:59
...

很有意思的贪心题。
有两种东西,一个消耗2,一个消耗1,各自有自己的属性val,开始有v可以消耗,问怎么消耗val最大。
设数组a存放消耗为1的,数组b存放消耗为2的。
一开始想的贪心策略是:先对数组a和b从大到小排序,每次比较数组a中的2个(如果有两个的话)和b中的一个哪个大,更新答案,最后特殊处理一下a只剩1个的情况。但是这样有一个问题:比如a中元素是5,3,3,b中元素是7,,v=3。按照最初的思路程序是先取5和3,v-2变成1,再取3,最终结果是11。但是如果取7和5的话会得到12。所以思路错误。
正确思路是先把消耗为2的都放进答案里面,然后放消耗为1的(如果有剩余的空间),然后维护答案,比较a中最大的两个和b中最小的那一个,需要强调的是,不用考虑a中的一个元素的值比b中的元素的值大的情况(想一想,为什么)。最后处理一下边界情况就AC啦啦啦----

#include <bits/stdc++.h>
using namespace std;
struct node{
	int val ;
	int id;
}a[101010],b[101010]; 
int v,n,num1,num2,t1,t2,pos1,pos2,f,tot;
set<int> ans;
int cmp(const node & c ,const node & d){
	return c.val>d.val;
} 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>v; 
	for(int i = 1;i<=n;i++){
		cin>>t1>>t2;
		if(t1==1) a[num1++] = {t2,i};
		else b[num2++] = {t2,i};
	}
	sort(a,a+num1,cmp);
	sort(b,b+num2,cmp);
	for(pos2;pos2<num2&&v>1;pos2++) {
		ans.insert(b[pos2].id);
		tot += b[pos2].val;
		v -= 2;
	}
	for(pos1;pos1<num1&&v>0;pos1++){
		ans.insert(a[pos1].id);
		tot += a[pos1].val;
		v--; 
	}
	for(pos2--;pos2>=0;pos2--){
		if(pos1>=num1) break;
		if(pos1<num1-1) {
			if(a[pos1].val+a[pos1+1].val>b[pos2].val) {
				tot += (a[pos1].val+a[pos1+1].val - b[pos2].val);
				ans.erase(b[pos2].id);
				ans.insert(a[pos1].id);ans.insert(a[pos1+1].id);
				pos1 += 2;
			}
			else break;
		}
		else if(a[pos1].val>b[pos2].val){
			tot += (a[pos1].val-b[pos2].val);
			ans.erase(b[pos2].id);
			ans.insert(a[pos1].id);
			pos1++; 
		}
	}
	cout<<tot<<endl;
	for(set<int>::iterator it = ans.begin();it!=ans.end();it++)
		cout<<*it<<' ';
	return 0;
} 
相关标签: Codeforces