题目看不懂

#include <iostream> #include <algorithm> using namespace std; const int N=100001; struct stu{ double w; double v; double wv; }a[N]; bool cmp(stu x,stu y){ return x.wv>y.wv; } int main(){ int k; cin>>k; while(k--){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i].w>>a[i].v; a[i].wv=a[i].v/a[i].w; } sort(a+1,a+n+1,cmp); double sum=0; for(int i=1;i<=m;i++){ if(n>=a[i].w){ sum+=a[i].v; } else{ sum+=n*a[i].wv; } n-=a[i].w; if(n<=0){ break; } } printf("%.2f\n",sum); } return 0; }

#include <iostream> #include <algorithm> using namespace std; struct stu{ double w; double v; double wv; }; bool cmp(stu x,stu y){ return x.wv>y.wv; } int main(){ int k; cin>>k; while(k--){ int n,m; cin>>n>>m; stu a[m]; for(int i=1;i<=m;i++){ cin>>a[i].w>>a[i].v; a[i].wv=a[i].v/a[i].w; } sort(a+1,a+n+1,cmp); double sum=0; for(int i=1;i<=m;i++){ if(n>=a[i].w){ sum+=a[i].v; } else{ sum+=n*a[i].wv; } n-=a[i].w; if(n<=0){ break; } } printf("%.2f",sum); } return 0; }

ACGO欢乐赛27没了，我查看了我报名的竞赛，显示没有欢乐赛27。

#3，9，10 有BUG

有点难

5 只要输出一个5，你就AC了。

多重背包问题 目录 1——问题概览 2——从"01"到"多重" 3——多重背包的时间优化(二进制优化) 4——总结 问题概览 难度：普及 题目：洛谷P1776宝物筛选、ACGO A20907 本文以宝物筛选作为多重背包的讲解，我们将题意简化为下面的描述： 有一个背包容量为WWW，还有nnn种商品 它们的重量分别为w1,w2...wnw_1,w_2...w_nw1 ,w2 ...wn ，价值为v1,v2...vnv_1,v_2...v_nv1 ,v2 ...vn ，个数为m1,m2...mnm_1,m_2...m_nm1 ,m2 ...mn 求在不超过背包的容量WWW下所能获得的最大价值 从"01"到"多重" 多重背包不同于完全背包和01背包的，它对于任一物品iii只能够拿限定的mim_imi 件 在01背包的讲解中我们说01背包是背包问题的基础，而多重背包就可以转换为01背包 看到这个题目的时候我们可以很快想出一个方法，设kik_iki 为第iii件物品拿的数量，通过forforfor循环把多重问题转换为许多01背包问题 就是对于第iii件物品，可用资金为jjj，拿取数量为kkk时有拿或不拿两种状态 代码如下 这样是可以通过低数据的情况，因为时间是O(WΣ mi)O(W\Sigma\ m_i)O(WΣ mi )，但根据数据最大运算量为4×1094\times10^94×109，对于大数据必TLE 多重背包的时间优化(二进制优化) 为了AC这题，我们必须进行优化，在上面的算法当中我们把每一个物品都拆成了Σ mi\Sigma\ m_iΣ mi 件物品，这样运算量肯定很大 那我们是否可以通过减少拆分来使运算量变少呢？Absolutely YES !Absolutely\ YES\ !Absolutely YES ! 但如何定义拆分的量呢？我们知道定理任何整数都能分解成2的幂之和 因此可以将mim_imi 拆分为多个2k2^k2k相加，避免了出现数据不一致的情况 例如给出一件物品i,wi=1,vi=1,mi=600i,w_i=1,v_i=1,m_i=600i,wi =1,vi =1,mi =600，按照新算法分解为下面的形式 编号iii wiw_iwi 重量 viv_ivi 价值 选或不选 111 111 111 待定 222 222 222 待定 333 444 444 待定 444 888 888 待定 555 161616 161616 待定 666 323232 323232 待定 777 646464 646464 待定 888 128128128 128128128 待定 999 256256256 256256256 待定 101010 898989 898989 待定 可以很直观感受到，如果按照先前的算法我们是要600次计算，而现在只需要10次，时间优化到了O(WΣlog⁡mi)O(W\Sigma\log m_i)O(WΣlogmi ) 这样的方法叫"二进制优化"，毕竟任一数都可转换为二进制形式而且分解2的幂相加这一步很像二进制位的拆分 代码如下，写法应该肥肠容易理解吧 总结 不论是多重背包还是完全背包，在转换后依然是使用了01背包的思想，可见01背包的重要性

#include<bits/stdc++.h> using namespace std; int a[110],b[110]; int n; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; sort(a+1,a+n+1); sort(b+1,b+n+1); int cnt=0; int j=1; for(int i=1;i<=n&&j<=n;i++,j++){ while(i<=n&&b[j]>=a[i]){ i++; } if(i<=n) cnt++; } cout<<(2*cnt-n)*200; }

高精除高精👍

这样写RE😭😭😭

链接描述

啊 啊 啊 啊 啊 过不了 啊 啊 啊 啊 啊

甚至 O(n+m)O(n+m)O(n+m)

1.学习网站 2.扫雷 3.购物网站 4.编程学习网站

我做题的时候巴不得史蒂夫嗝屁！！！！！！！！！！！！！！！！！！！！！！！1