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

Codeforces 3B

程序员文章站 2022-05-09 17:41:28
...

题意:用一个truck运两种船,一种占空间1m^3(type 1), 一种占空间2m^3(type 2), 给定truck的容量v(以m^3计)和一个船运载量的list,求出truck所运船的最大运载量和达到最大运载量时运载的船集合(有多个可选的集合时print任意一个集合)

分析:读完了题直觉上感觉是个背包问题,但是题目里的标签显示的是greedy + sort, 根据标签的提示往greedy的方向想,想出了greedy的解法

解法:首先分别将两种船按运载量从大到小排序k[] c[],然后分析一下,算法如下:

        1)如果v是奇数,转2);否则转3)

        2)如果有type1的船,那么就找出k[0]; //用反证法可以证明,v是奇数时要想达到最大容量,就一定要把这条船加入集合;转3)

       3) v现在是偶数,一个while循环;每次拿两个还没加入集合的运载量最大的type1的船的运载量和与一个还没加入集合的运载量最大的type2的船相比,选大的加到集合里;直到有一种船的数量不够这么比或者truck被填满;

      4)如果truck没有被填满,在保证不会超出truck容量的前提下,每次加入一个容量最大的船直到船都加入或者truck已满


细节问题:

  1. 因为数组开销了runtime error了7,8次。。。

  2. 排序时要连着船的ID一起排

  3. 题中对于集合的打印方式没有明确说明,但是看结果,应该是空格分割ID,所有的ID在一行里

    代码如下:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int maxn = 100005;
class element{
	public:
	int v;
	int id;
	bool operator < (const element & e) const{
		return v > e.v;
	}
};
element k[maxn];
element c[maxn];
vector<int> recid;
int main(){
	int n;
	int v;
	cin >> n >> v;
	int t, p;
	long long kidx = 0, cidx = 0;
	memset(k, 0, sizeof(k));
	memset(c, 0, sizeof(c));
	for(int i = 0;i < n; ++i){
	       cin >> t >> p;
               switch(t){
		       case(1):
			       k[kidx].v = p;
			       k[kidx++].id = i + 1;
			       break;
		       case(2):
			       c[cidx].v = p;
			       c[cidx++].id = i + 1;
			       break;
	       }
	}
	sort(k,k+kidx);
	sort(c,c+cidx);
        long long res = 0;
	int kp = 0, cp = 0;
	if(v % 2 != 0 && kidx > kp){
		v -= 1;
		recid.push_back(k[kp].id);
		res += k[kp].v;
		kp++;
	}
	while(v > 0 && kp < kidx && ((kp + 1) < kidx) && cp < cidx){
		if(c[cp].v >= (k[kp].v + k[kp + 1].v)){
			res += c[cp].v;
			recid.push_back(c[cp].id);
			cp++;
		}
		else{
			res += k[kp].v + k[kp+1].v;
			recid.push_back(k[kp].id);
			recid.push_back(k[kp+1].id);
			kp += 2;
		}
		v = v - 2;
	}
	if(v > 0){
		if(cp >= cidx){
			//cp >= cidx;
			while(v > 0 && kp < kidx){
				res += k[kp].v;
				recid.push_back(k[kp++].id);
				v -= 1;
			}
		}
		else{
			while(v > 1 && (cp < cidx || kp < kidx)){
				int tmp1, tmpid1, tmp2, tmpid2;
				if(cp < cidx){
					tmp1 = c[cp].v;
					tmpid1 = c[cp].id;
				}
				else{
					tmp1 = 0;
					tmpid1 = 0;
				}
				if(kp < kidx){
					tmp2 = k[kp].v;
					tmpid2 = k[kp].id;
				}
				else{
					tmp2 = 0;
					tmpid2 = 0;
				}
				if(tmp1 > tmp2){
					res += tmp1;
					recid.push_back(tmpid1);
					cp++;
					v -= 2;
				}
				else{
					res += tmp2;
					recid.push_back(tmpid2);
					kp++;
					v -= 1;
				}
			}
			if( kp < kidx){
				//v <= 1
				while(v > 0 && kp < kidx){
					res += k[kp].v;
					recid.push_back(k[kp].id);
					++kp;
					v -= 1;
				}
			}
		}		
	}



	cout << res << endl;
	sort(recid.begin(), recid.end());
	int vecsize = recid.size();
	for(int i = 0; i < vecsize; ++i){
		if(recid[i] == 0){
			continue;
		}
		cout << recid[i] << " ";
	}
	cout << endl;
	return 0;
}


转载于:https://my.oschina.net/u/1421373/blog/378620