网站开发工具的是什么,行政法规,上海微信网站,网页此站点不安全int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题 为一个小老鼠准备了M磅的猫粮#xff0c;准备去和看守仓库的猫做交易#xff0c;因为仓库里有小老鼠喜欢吃的五香豆#xff0c;第i个房间有J[i] 磅的五香豆#xf… int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题 为一个小老鼠准备了M磅的猫粮准备去和看守仓库的猫做交易因为仓库里有小老鼠喜欢吃的五香豆第i个房间有J[i] 磅的五香豆并且需要用F[i]磅的猫粮去交换求老鼠最多可换多少豆若五香豆不能全换猫粮按比例换。 Sample Input 5 3 ——M猫粮 N房间 7 2 ——五香豆 猫粮 4 3 5 2 -1 -1 —— 结束 Sample Output 13.333 由按比例换7/23.5 4/31.333... 5/22.5 3.5最大 排序一次换——751.333313.333 初识贪心
在对问题求解时总是做出在当前看来是最好的选择。
也就是说不从整体上加以考虑所作出的仅仅是在某种意义上的局部最优解是否是全局最优需要证明。 例题
1.田忌赛马 每个马跟比自己弱的程度最小的马
1.排序
2.蓝色最大和红色最大比较看蓝色能不能比过红色若比不过拿蓝色最小的跟红色比
3.拿蓝色最大跟红色第二大的比...能比就比不能就继续拿最差的跟最好的比 反证法上大分~事件序列问题 已知N个事件的发生时刻和结束时刻。 一些在时间上没有重叠的事件可以构成一个事件序列如事件{2810}。 事件序列包含的事件数目称为该事件序列的长度。 请编程找出一个最长的事件序列。 至少存在一个最长事件序列包含最早结束事件最早结束事件是0
反证法证明上句
假设所有最长事件序列都不包含最早结束事件只要证明这个假设是错的原命题得证
任取一个所谓的最长事件序列把第一个事件去掉换掉事件0肯定跟后面都不冲突因为换上的是最早结束的时间原来都不冲突现在更不冲突
证明完后选中最早结束事件0 后面我做类似的每次找一个最早结束的事件只要和前面的不冲突的都选中 2.搬桌子 一个公司要做调整搬桌子房间有400个一边是单号一边双号 走廊很窄只通过1个桌子过 输入 第二行趟数 第三行房间号10号搬到20号 每趟搬要10min不重叠可以同时搬要10min重叠要分开搬 法一与上题的思想差不多只不过改成了最早开始事件找开始最早的
法二统计每个区间在时间轴上的重叠次数并找出最大重叠次数的区间。
#include bits/stdc.h
using namespace std;int main() {int t, i, j, N, P[200]; // t是测试用例的数量N是每个测试用例的区间数量int s, d, temp, k, MAX; // s和d是区间的起点和终点MAX用于记录最大重叠次数cin t;for (i 0; i t; i) {// 初始化P数组用于记录每个时间点的重叠次数for (j 0; j 200; j)P[j] 0;cin N; // 读取当前测试用例的区间数量for (j 0; j N; j) {cin s d; // 读取区间的起点和终点s (s - 1) / 2; // 将起点转换为数组索引d (d - 1) / 2; // 将终点转换为数组索引// 如果起点大于终点交换它们if (s d) {temp s;s d;d temp;}// 在区间[s, d]内的每个时间点增加计数for (k s; k d; k)P[k];}// 找到最大重叠次数MAX -1;for (j 0; j 200; j)if (P[j] MAX)MAX P[j];// 输出最大重叠次数乘以10cout MAX * 10 endl;}return 0;
} 3.删数问题 已知一个长度不超过240位的正整数n其中不含有效字0去掉其中任意ss小于n的长度个数字后将剩下的数字按原来的左右次序组成一个新的正整数。 给定n和s请编程输出最小的新正整数。 Sample Input 178543 4 Sample Output 13 法一从左到右扫描逆序对删掉左边的数若没有逆序对删掉最后一位数
1 7 8 5 4 3 —— 1 7 5 4 3 ——1 5 4 3 ——1 4 3 —— 1 3
1 2 3 4 4.青蛙的邻居 每个湖泊都有一个青蛙如果两个湖泊之间有水渠相连我们认为两个青蛙他们为邻居 问你可以画出这个湖泊分布图吗 Sample Input 3 7 —— 青蛙个数 4 3 1 5 4 2 1 —— 第一个青蛙有4个邻居第二个青蛙有3个邻居.... 6 4 3 1 4 2 0 6 2 3 1 1 2 1 Sample Output YES NO YES 用以下知识可解决 离散数学可图性判定
两个概念
1.度序列若把图A所有顶点的度数排成一个序列S则称S为图A的度序列。
度一个顶点他有几条边度就是几 图A 2 3 1 1 1 就是度序列 2.序列是可图的一个非负整数组成的有限序列如果是某个无向图的度序列则称该序列是可图的。
若度序列2 3 1 1 1可以画出图A就是可图的 Havel-Hakimi定理解决可读性判定 之后再排序3 2 2 2 1
做一趟排序一次只要出现负数就不可能了图画不出来最后全变成0可以画 Havel定理的解释——加加减减与图的对应关系_哔哩哔哩_bilibili 特别说明
若要用贪心算法求解某问题的整体最优解必须首先证明贪心思想在该问题的应用结果就是最优解
在使用贪心算法解决问题时必须首先证明贪心策略能够导致整体最优解。贪心算法通常通过每一步选择局部最优解来构建全局解但并非所有问题都适合使用贪心算法因此证明其正确性是关键。
说明理由 若某货币系统有三种币值分别为一角、五分和一分要找1角5分 求最小找币数时是否可以用贪心法求解 可以先用最大的能找几个找几个 如果将这三种币值改为一种一分、五分和一分要找1角5分 是否还可以使用贪心法求解 不行 因为他不成倍数 贪心算法的常见操作
贪心总是要找最大的、最小的、最划算的往往要排序
