天津做网站的公司怎么样重庆市建设信息网站

当前位置： 首页 > news >正文

天津做网站的公司怎么样,重庆市建设信息网站,通过WordPress开发的主题,网络安全防护高级贪心算法 一、P1803 活动安排1. 审题2. 思路2.1 最优区间挑选方法2.2 分配时间方法2.3 排序方法 3. 参考答案 二、P1094 纪念品分组1. 审题2. 思路2.1 每组多少个方法2.2 搭配的方法 3. 参考答案 三、村民打水1. 审题2. 思路3. 参考答案 四、习题1. 服务等待1.1 审题1.2 参… 高级贪心算法 一、P1803 活动安排1. 审题2. 思路2.1 最优区间挑选方法2.2 分配时间方法2.3 排序方法 3. 参考答案 二、P1094 纪念品分组1. 审题2. 思路2.1 每组多少个方法2.2 搭配的方法 3. 参考答案 三、村民打水1. 审题2. 思路3. 参考答案 四、习题1. 服务等待1.1 审题1.2 参考答案 2. 春节糖果2.1 审题2.2 思路2.3 参考答案 3. LC452 气球射击3.1 审题3.2 思路3.3 参考答案 彩蛋 一、P1803 活动安排

1. 审题 题目描述 春节快要到了耶斯莫拉大酒店在最近几天要举办 n n n 个活动这些活动都需要使用酒店的大礼堂而在同一时间礼堂只能被一个活动使用。由于有些活动时间上有冲突酒店管理人员只好让一些活动放弃使用礼堂而使用其他小的餐厅。现在给出n个活动使用礼堂的起始时间 b e g i n i begin_i begini​ 和结束时间 e n d i end_i endi​ ( b e g i n i e n d i ≤ 32767 begin_i end_i \le 32767 begini​endi​≤32767)请你帮助酒店管理人员安排一些活动来使用礼堂要求安排的活动尽量多。假设没有重新布置礼堂时间的消耗即某个时间点完成活动的瞬间就可以开始下一个活动。 输入描述 第一行一个整数 n n n( n ≤ 1000 n \le 1000 n≤1000)接下来的 n n n 行每行两个整数第一个 b e g i n i begin_i begini​ 第二个是 e n d i end_i endi​ ( b e g i n i e n d i ≤ 32767 begin_i end_i \le 32767 begini​endi​≤32767)。 输出描述 输出最多能安排的活动个数。 样例1 输入 11 3 5 1 4 12 14 8 12 0 6 8 11 6 10 5 7 3 8 5 9 2 13输出 4提示 无 2. 思路 2.1 最优区间挑选方法 开始时间 不应该这么直接因为开始时间的早晚会导致活动少不是最优解。 所用时间 如果在两个活动执行区间内有一个更短时间的活动则错过了几个活动不是最优解。 结束时间 结束时间越早说明后面剩余的连续时间越多 是最优解。 2.2 分配时间方法 首先一定要从一个区间开始遍历因为如果这个区间包含了下个区间那么选择这个区间不如选择下一个区间划算选下个区间还能节省几个点来用于其他区间的选择。 2.3 排序方法 通过结束时间从小到大进行排序需要用到结构体 struct 。 3. 参考答案 #include iostream #include algorithm using namespace std;int n, rem, ans 1;struct Node {int l, r; }a[1005];bool cmp(Node a, Node b) {return a.r b.r; }int main() {cin n;for (int i 1; i n; i){cin a[i].l a[i].r;}sort(a1, an1, cmp);int rem a[1].r;for (int i 2; i n; i){if (a[i].l rem){ans;rem a[i].r;}}cout ans;return 0; }二、P1094 纪念品分组
2. 审题 题目描述 元旦快到了校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡他要把购来的纪念品根据价格进行分组但每组最多只能包括两件纪念品 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品乐乐希望分组的数目最少。 你的任务是写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。 输入格式 输入文件 gift.in 共 n 2 n2 n2 行 第一行包括一个整数 w w w为每组纪念品价格之和的上限。 第二行为一个整数 n n n表示购来的纪念品的总件数 G G G。 第 3 n 23 n 2 3 ~ n 23 ~ n 2 3 n23 n2 行每行包含一个正整数 P i P_i Pi​ 表示所对应纪念品的价格。 输出格式 输出文件 gift.out 一个整数即最少的分组数目。 样例1 输入 100 9 90 20 20 30 50 60 70 80 90输出 6提示 50 % 50\% 50% 的数据满足 1 ≤ n ≤ 15 1\le n\le15 1≤n≤15 100 % 100\% 100% 的数据满足 1 ≤ n ≤ 3 × 1 0 4 1\le n\le3\times10^4 1≤n≤3×104 80 ≤ w ≤ 200 80\le w\le200 80≤w≤200 2. 思路 2.1 每组多少个方法 当和 ≤ w \le w ≤w 的时候优先 2 2 2 个一组。 2.2 搭配的方法 优先让危险的数字越贵找不危险的数字越便宜也就是大找小。 如果超过 w w w 则优先让大的组成 1 1 1 组。 3. 参考答案 #include iostream #include cstdio #include algorithm using namespace std;int w, n, cnt; int num[30005];int main() {freopen(gift.in, r, stdin);freopen(gift.out, w, stdout);cin w n;for (int i 1; i n; i){cin num[i];}sort(num1, numn1);int i 1, j n;while (i j){// 贵的配便宜的 if (num[j] num[i] w){cnt;j–;i;}// 贵的单独一组 else{cnt;j–;}}cout cnt;fclose(stdin);fclose(stdout);return 0; }三、村民打水
3. 审题 题目描述 在一个小村子里生活着 n n n 户人家。由于村里只有一口井所以他们每天早上一户人家派一个人在这一口井前排队打水。由于每家的水桶大小不同所以每个人的打水时间也不同。假如每个人打水的时间为 T i T_i Ti​请你编程找出这 n n n 个人排队的一种顺序使得 n n n 个人的平均等待时间最小。 输入描述 共两行第一行为 n n n第二行分别表示第 1 1 1 个人到第 n n n 个人每人的打水时间 T i T_i Ti​每个数据之间有 1 1 1 个空格。 输出描述 共两行第一行为一种排队顺序即1到n的一种排列第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。 样例1 输入 10 56 12 1 99 1000 234 33 55 99 812 输出 3 2 7 8 1 4 9 6 10 5 291.90提示 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105 1 ≤ T i ≤ 1 0 6 1 \le T_i \le 10^6 1≤Ti​≤106不保证 T i T_i Ti​ 不重复 当 T i T_i Ti​ 重复时按照输入顺序即可sort 是可以的 2. 思路 计算每个人的等待时间并且累加得到总的等待时间 a n s ans ans。对于第 i i i 个人他的等待时间为 ( n − i ) ∗ t i (n-i) * t_i (n−i)∗ti​其中 n n n 是总人数 t i t_i ti​ 是第 i i i 个人的打水时间。 3. 参考答案 #include iostream #include iomanip #include algorithm using namespace std;int n; double ans;struct Node {int idx;int t; }person[100005];bool cmp(Node a, Node b) {if (a.t ! b.t){return a.t b.t;}return a.idx b.idx; }int main() {cin n;for (int i 1; i n; i){person[i].idx i;cin person[i].t;}sort(person1, personn1, cmp);for (int i 1; i n; i){ans person[i].t * (n-i);cout person[i].idx ;}ans / n;cout endl fixed setprecision(2) ans;return 0; }四、习题
4. 服务等待 1.1 审题 题目描述 小明新店开业免费为顾客进行按摩服务现在已经排了一个有 n n n 个人的队伍其中第 i i i 个人需要 t[i] 分钟来服务期间后面的人就要等着。如果一个人等待的时间大于了他被服务的时间他就会失望就会离开队伍。 你的任务是重排队伍使失望的人尽量的少并输出最多有多少个不失望的人。 输入描述 第 1 1 1 行一个整数 n n n表示队伍人数。 接下来 n n n 行每行一个整数表示第i个人的服务时间 t [ i ] t[i] t[i] 。 输出描述 输出一行为一个整数表示最多不失望的人数。 样例1 输入 5 15 2 1 5 3输出 4提示 1 ≤ n ≤ 1 0 5 1 ≤ t [ i ] ≤ 1 0 3 1 \le n \le 10^51 \le t[i] \le 10^3 1≤n≤1051≤t[i]≤103 1.2 参考答案 #include iostream #include algorithm using namespace std;int n, cnt, wait; int t[100005];int main() {cin n;for (int i 1; i n; i){cin t[i];}sort(t1, tn1);for (int i 1; i n; i){if (wait t[i]){cnt;wait t[i];}}cout cnt;return 0; }2. 春节糖果 2.1 审题 题目描述 春节快到了王老师给同学们准备了春节糖果让胡图图负责糖果的发放工作。王老师准备的不同糖果美味度不同为使得各位同学所获得的糖果美味度相对均衡图图需要把购来的糖果根据美味度进行分组但每组最多只能包括两份糖果并且每组糖果的美味度之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有糖果图图希望分组的数目最少。 由于胡图图比较糊涂所以请你帮图图写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。 输入描述 输入文件名 gift.in 共 n 2 n2 n2 行 第 1 1 1 行包括一个整数 w w w为每组糖果美味度之和的上限。 第 2 2 2 行为一个整数 n n n表示购来的糖果的总件数。 第 3 n 2 3~n2 3 n2 行每行包含一个正整数 p i p_i pi​ ( 5 ≤ p i ≤ w 5 \le p_i \le w 5≤pi​≤w)表示所对应糖果的美味度。 输出描述 输出文件名 gift.out 仅一行包含一个整数即最少的分组数目。 样例1 输入 100 9 90 20 20 30 50 60 70 80 90输出 6提示 50 % 50\% 50%的数据满足 1 ≤ n ≤ 15 1 \le n \le 15 1≤n≤15 100 % 100\% 100%的数据满足 1 ≤ n ≤ 3 × 1 0 4 , 80 ≤ w ≤ 200 1 \le n \le 3 \times 10^4, 80 \le w \le 200 1≤n≤3×104,80≤w≤200 2.2 思路 将购来的糖果按照美味度从小到大进行排序。使用双指针尺取来选择糖果组成分组。设置两个指针 l l l 和 r r r分别指向糖果数组的第一个和最后一个元素。每次迭代中判断左指针和右指针所指的糖果美味度之和是否小于等于给定的美味度上限 w w w。 如果是表示可以将这两个糖果放在同一组内我们将左指针向右移动一位右指针向左移动一位。如果不是表示这两个糖果无法放在同一组内我们只能将右指针向左移动一位继续成组。 在每次迭代中无论是否能放入同一组内我们都将分组数目 c n t cnt cnt 自增。当左指针超过右指针时表示所有的糖果都已经处理完毕此时 c n t cnt cnt 的值为最少的分组数目。 这种算法通过贪心的策略每次选择美味度最小和最大的糖果进行配对以保证尽可能多的糖果被分组。同时通过排序操作使得每次选择到的糖果的美味度是当前剩余糖果中最小的这样有利于后续的分组过程。 2.3 参考答案 #include iostream #include cstdio #include algorithm using namespace std;int w, n, cnt, sum; int candies[30005];int main() {freopen(gift.in, r, stdin);freopen(gift.out, w, stdout);cin w n;for (int i 1; i n; i){cin candies[i];}sort(candies1, candiesn1);int l 1, r n;while (l r){if (candies[l] candies[r] w){l;r–;}else{r–;}cnt;}cout cnt;fclose(stdin);fclose(stdout);return 0; }3. LC452 气球射击 3.1 审题 题目描述 游乐园举办了一场射气球的比赛如果谁能使用最少的弓箭数量引爆所有气球则会得到最佳射手奖。 规则如下 在二维空间中有 n n n 个直径不同的球形气球对于每个气球提供的是水平方向上气球直径的开始和结束坐标。由于气球是被水平牵引的所以Y坐标并不重要因此只要知道气球直径的开始和结束的X坐标就足够了。每个气球的直径的开始坐标一定小于结束坐标。 一支弓箭可以沿着 X X X 轴从不同点完全垂直地射出。在坐标 X X X 处射出一支箭若有一个气球的直径的开始和结束坐标为 ( a , b ) (a,b) (a,b)只要满足 a ≤ X ≤ b a ≤ X ≤ b a≤X≤b则该气球会被引爆。 可以射出的弓箭的数量没有限制。弓箭一旦被射出之后可以无限地前进。 如果要将所有气球全部被引爆最少需要多少支弓箭呢 输入描述 第一行有一个正整数 n n n( 1 ≤ n ≤ 1000 1\le n\le1000 1≤n≤1000) 接下来有 n n n 行每一行有 2 2 2 个正整数 a a a b b b分别表示气球直径的开始坐标和结束坐标 1 ≤ a , b ≤ 32767 1\le a,b\le 32767 1≤a,b≤32767。 输出描述 单独一行表示引爆所有气球所需弓箭的最小数量。 样例1 输入 4 10 16 2 8 1 6 7 12输出 23.2 思路 将气球的坐标按照结束点的大小进行排序。设置射击数量变量 c n t cnt cnt 为 1 1 1同时设置一个变量 e n d end end 表示当前射击的结束点。遍历气球的坐标数组对于当前的气球坐标 ( s t a r t , e n d start, end start,end) 如果 s t a r t e n d start end startend表示当前气球的起始点在之前的射击结束点之后说明需要增加一个射击的数量同时更新 e n d end end 为当前气球的结束点。否则表示当前气球的起始点在之前的射击结束点之前说明当前气球可以用同一支箭射击不需要增加射击的数量但是需要更新 e n d end end 为当前气球的结束点。 当遍历结束后 c n t cnt cnt 的值即为最少需要的射击数量。 3.3 参考答案 #include iostream #include algorithm using namespace std;int n, cnt 1;struct Node {int start, end; }balloon[1005];bool cmp(Node a, Node b) {return a.end b.end; }int main() {cin n;for (int i 1; i n; i){cin balloon[i].start balloon[i].end;}// 按照结束点排序sort(balloon1, balloonn1, cmp);int end balloon[1].end;for (int i 2; i n; i){// 如果当前气球起始点再之前的结束点之后if (balloon[i].start end){cnt; // 增加射击数量end balloon[i].end; // 更新射击结束点}}cout cnt;return 0; }彩蛋 下期预告 下期知识点总结明天将会给大家刷 7 道很难的题也就是 魔鬼刷题日
   C玩法技巧 多行输出的时候用函数 R()
   cout R(#### ## ## #### …)