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已满
细节问题:
因为数组开销了runtime error了7,8次。。。
排序时要连着船的ID一起排
-
题中对于集合的打印方式没有明确说明,但是看结果,应该是空格分割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
上一篇: 智联招聘爬虫
推荐阅读
-
『ACM C++』 Codeforces | 1003C - Intense Heat
-
Codeforces 939A题,B题(水题)
-
树莓派3B的WiFi中文乱码问题无法连接_解决方案:
-
CodeForces 29D Ant on the Tree
-
Codeforces Global Round 9-C. Element Extermination
-
codeforces 712B Memory and Trident
-
CodeForces 962D Merge Equals
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
CodeForces 1326E - Bombs
-
CodeForces 612E Square Root of Permutation