北京制作网站多少钱,mvc5网站开发,商城网站流量,天津百度推广排名Problem - B - Codeforces
题目大意#xff1a;给物品数量 n n n#xff0c;体积为 v ( 0 ≤ v ≤ 1 e 9 ) v_{(0 \le v \le 1e9)} v(0≤v≤1e9)#xff0c;第一行读入 n , v n, v n,v#xff0c;之后 n n n行#xff0c;读入 n n n个物品#xff0c;之后每行依次是体…Problem - B - Codeforces
题目大意给物品数量 n n n体积为 v ( 0 ≤ v ≤ 1 e 9 ) v_{(0 \le v \le 1e9)} v(0≤v≤1e9)第一行读入 n , v n, v n,v之后 n n n行读入 n n n个物品之后每行依次是体积和价值其中体积要么是1要么是2。要求输出价值和最大且依次输出所选物品的编号。
思路发现体积 v v v很大用01背包一定不行01背包优化的事件复杂度是 O ( v ) O(v) O(v)也过不去。但是发现物品的体积要么是1要么是2。我们可以将物品按其体积分为两类分别表示体积为1的物品和体积为2的物品。之后对于相同体积的物品来说我们优先考虑其价值最大的那个所以要对物品进行排序。之后枚举物品体积为1的数量 i i i得到在物品体积为1的数量 i i i的条件下得到的最大值不断的进行更新即可。
代码如下
void solve() {int n,V; cinnV;// [0, 0] - 物品价值物品编号vectorarrayint,2 t1, t2;t1.push_back({0, 0});t2.push_back({0, 0});for(int i 0; i n; i) {int v, w; cinvw;if(v 1) t1.push_back({w, i 1});else t2.push_back({w, i 1});}// 得到物品体积为1的数量和2的数量int len1 t1.size() - 1, len2 t2.size() - 1;// 对物品按照价值从大到小进行排序sort(t1.begin() 1, t1.end(), [](auto pre, auto suf) {return pre[0] suf[0];});sort(t2.begin() 1, t2.end(), [](auto pre, auto suf) {return pre[0] suf[0];});// 得到体积为2的物品的前缀和vectorint pre(len2 1);for(int i 1; i len2; i) {pre[i] pre[i - 1] t2[i][0];}// 最大值当前体积为1的物品之和int ma 0, sum 0;// 最大值时体积为的个数和体积为2的个数int ans1 0, ans2 0;// 枚举体积为1的数量得到最大值for(int i 0; i len1; i) {if(i V) break;int j min( (V - i) / 2, len2);sum t1[i][0];if(sum pre[j] ma) {ma sum pre[j];ans1 i; ans2 j;}}// 输出即可coutma\n;for(int i 1; i ans1; i) coutt1[i][1] ;for(int i 1; i ans2; i) coutt2[i][1] ;
}刚开始写的时候发现定义比较麻烦就用了map进行映射发现要处理边界问题还不如上面简介呢
void solve() {int n,v; cinnv;mapint, vectorarrayint,2 mp;for(int i 0; i n; i) {int v,w; cinvw;mp[v].push_back({w, i 1});}for(int i 1; i 3; i) {sort(all(mp[i]), [](auto pre, auto suf) {return pre[0] suf[0];});}int vlen2 mp[2].size();vectorint pre(vlen2 1);auto v2(mp[2]);for(int i 0; i vlen2; i) {pre[i 1] pre[i] v2[i][0];}int sum 0, ma 0, need1 0, need2 0;auto v1(mp[1]);int vlen1 n - vlen2;ma pre[min(v / 2, vlen2)]; need2 min(v / 2, vlen2);for(int i 1; i vlen1; i) {if(i v) break;sum v1[i-1][0];int j min( (v - i) / 2, vlen2);if(sum pre[j] ma) {ma sum pre[j];need1 i; need2 j;}}coutma\n;for(int i 0; i need1; i) {coutv1[i][1] ;}for(int i 0; i need2; i) {coutv2[i][1] ;}
}
