ps做简洁大气网站,中国建设银行安徽省分行网站,厦门网站网页设,黄山旅游攻略自驾游首先用最最最经典的部分背包问题来引入贪心的思想。 由题意可知我们需要挑选出价值最大的物品放入背包#xff0c;价值即单位价值。
我们需要计算出每一堆金币中单位价值。金币的属性涉及两个特征#xff0c;重量和价值。
所以我们使用结构体。
上代码。
#include i…首先用最最最经典的部分背包问题来引入贪心的思想。 由题意可知我们需要挑选出价值最大的物品放入背包价值即单位价值。
我们需要计算出每一堆金币中单位价值。金币的属性涉及两个特征重量和价值。
所以我们使用结构体。
上代码。
#include iostream
#include algorithm
#include cstdio
using namespace std;
struct Item {int c, w;
};//定义结构体c代表价值w代表重量
Item item[1010];//创建结构体变量
bool cmp(Item a, Item b){//定义排序方式return a.w * b.c b.w * a.c;//单价的转换形式
}//排序函数说白了就是比性价比
int main() {int N, V;cin N V;for (int i 1; i N; i) {cin item[i].c item[i].w;}sort(item 1, item N 1, cmp);//输入后排序double ans 0;for(int i1; iN; i){if(V item[i].c){ans (double)item[i].w / item[i].c * V;//double强转V 0;break;}else{ans item[i].w;V - item[i].c;}}printf(%.2lf, ans);return 0;
} 第二种写法 class Item {//定义一个类里面包含价值和重量两个参数以方便创建vector数组
public:int w, v;//变量Item(int w, int v) :w(w), v(v) {//列表初始化}};
double solve(vectorint wei, vectorint val,int t)
{vectorItemans;//声明类型为Item的vector数组每一个元素包含两个变量for (int i 0; i wei.size(); i){ans.push_back(Item(wei[i], val[i]));//将价值和重量填入创建的Item类型数组}sort(ans.begin(), ans.end(), [](Item a, Item b) {return(double)a.v / a.w (double)b.v / b.w; });//对vector数组进行排序lamba表达式【】为定义排序的格式这里也可以定义一个bool函数来实现排序的方式double res 0;for (auto items : ans)//遍历{if (items.w t)//如果第一堆金币总重量小于背包重量全部放入{res items.v;t - items.w;}else {res (double)items.v / items.w * t;//将剩余的重量用最大的价值单价填入break;}}return res;
}int main()
{int n, t,w,v;cin n t;vectorintwei;//创建重量数组vectorintval;//创建价值数组for (int i 0; i n; i){cin w v;wei.push_back(w);val.push_back(v);}double ans solve(wei, val,t);printf(%.2lf, ans);
} 这一题选自洛谷p1223题根据题意我们可以知道要想得到最短的等待时间得先让排队时间少的先接水。下面介绍两种方法进行解决。
由于题目既要有接水时间又要有序号且这两个元素是对应同一个人所以我们第一种方法使用结构体。
上代码。
#include iostream
#include vector
#include algorithm
#includecstdio.husing namespace std;
struct human {int b, num;//输出的两个变量有联系用结构体
};
bool cmp(human a, human x)//定义比较的方式
{return a.b x.b;
}
int main()
{struct human ans[1001];int n, i, j;double time 0;cin n;for (int i 1; i n; i){cin ans[i].b;//每个人的时间ans[i].num i;//每个人对应的序号}sort(ans 1, ans n 1, cmp);for (int i 1; i n; i){cout ans[i].num ;}cout endl;for (j n - 1; j 1; j--){i n - j;//此时的总人数time ans[i].b * j;//当前人的等待时间要乘以此时的总人数}printf(%.2lf,time);return 0;
}
第二种方法不使用结构体使用vectorpair。
#include iostream//洛谷p1223
#include vector
#include algorithmusing namespace std;
int main() {int n;double sum 0;cin n;vectorpairint, int a(n);//既要记录每个人的序号也要记录每个人的时间定义vector的元素类型为pairfor (int i 0; i n; i) {cin a[i].first;//第一个为时间调用每一个为pair类型元素的firsta[i].second i 1;//第二个为序号调用每一个为pair类型元素的second}sort(a.begin(), a.end());//排序升序for (int i 0; i n; i) {sum a[i].first * (n - i - 1);//先排上的人后面所有人都要等待cout a[i].second ;}printf(\n%.2f, sum / n);return 0;
}
