浙江大学软件学院2020年保研上机模拟练习 7-4 Shopping With Coupons
目录
解题思路演进过程
第一次程序
第二次程序
第三次程序
解题思路演进过程
首先是题目的理解上：有n个商品，n张优惠券，实际上能买的商品个数最多就是n*n,为啥呢，这题默认是买一个商品必须用一张券，而且一个商品每张面值的券只能用一次。也就是，即使有1个6元的商品，当券对这个商品全部用过一次，即使有10元商品和最大面值3的券，也只能够选后者。
第一次我套用了0-1背包的动态规划，但是遗憾的是，由于背包容量(在本题是钱的数量大于10的6次方)，即使把真实价格按照从低到高排序，取前1000个，动规本身也会造成超时。
第二次我在计算每件商品实际要付出的价格时，程序是这么写的
int num = 0;
for(int i=0;i<n&&num<1000000;i++){for(int j=n-1;j>=0&&num<1000000;j--){int t = v[i]-c[j];pac[num++]=t;}
}此前，v和c都已经从低到高排序了，也就是只读入最小的前100w个，然后使用贪心，只要钱足够就买入。这次没有超时。但是有一个用例是答案错误。
分析可能有两个原因：1.贪心本身就不科学 2.以我刚刚的计算方法，得到的并不是真正最小的前100w个价格。
我尝试计算出所有可能的价格，进行排序，再取前100w个，很遗憾，2个超时，得分甚至更低。
我幡然醒悟，这题是追求最大商品个数，又不是价值，本来就不是动规问题，因此把价值从低到高一件件地往购物车里放就是能够得到最多商品数的策略。
问题就出在如何不超时地得到从低到高的价格排序，且我得到的100w是死的，也许它要100w+1呢？
也就是我的26分程序丢分点可能在于：1.不是严格的小到大价格排序 2.给出的价格排序满足时间复杂度但是剩余的钱还能买
怎么办？只能改成动态的。
友情外链：浙江大学软件学院2020年保研上机模拟练习
我参考上面那位仁兄的思路，主要改进的地方是，使用了优先队列，这样能让最低价格自动上到第一位，并且加入队列的准则是，加入上一个弹出商品次优的价格(如果还有更低的优惠券没用的话，要是没有就不管了)。
第一次程序
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<queue>using namespace std;const int maxn = 100010;
const int inf = 1000000+10;//即10^6vector<int> pac;//price after coupon
int dp[inf] = {0};int n,W;
int v[maxn],c[maxn];int main(){scanf("%d %d",&n,&W);for(int i=0;i<n;i++){int t;scanf("%d",&t);v[i] = t;}for(int i=0;i<n;i++){int t;scanf("%d",&t);c[i] = t;}for(int i=0;i<n;i++){for(int j=0;j<n;j++){int t = v[i]-c[j];pac.push_back(t);}}sort(pac.begin(),pac.end());for(int i=0;i<n*n;i++){for(int w = W;w>=pac[i];w--){dp[w] = max(dp[w-pac[i]]+1,dp[w]);}}int maxDp = -1;int maxNum = 0;for(int w = 0;w<=W;w++){if(dp[w]>maxNum){maxNum = dp[w];maxDp = w;}}printf("%d %d",maxNum,W-maxDp);return 0;
}第一次结果
第二次程序
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<queue>using namespace std;const int maxn = 100010;
const int inf = 1000000+10;//即10^6int pac[1000000];//price after coupon
int dp[inf] = {0};int n,W;
int v[maxn],c[maxn];int main(){scanf("%d %d",&n,&W);for(int i=0;i<n;i++){int t;scanf("%d",&t);v[i] = t;}sort(v,v+n);for(int i=0;i<n;i++){int t;scanf("%d",&t);c[i] = t;}sort(c,c+n);int num = 0;for(int i=0;i<n&&num<1000000;i++){for(int j=n-1;j>=0&&num<1000000;j--){int t = v[i]-c[j];pac[num++]=t;}}sort(pac,pac+num);int left = W;int iNum = 0;for(int i=0;i<num;i++){if(left>=pac[i]){left-= pac[i];iNum ++; }if(left<=0)break; }printf("%d %d",iNum,left);return 0;
}
第三次程序
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<map>
#include<vector>
#include<set>using namespace std;const int maxn = 100010;
const int SUP = 2000000000;int n,t;
int it[maxn],co[maxn];struct price{int itIdx,coIdx,sub;price(int _it,int _co):itIdx(_it),coIdx(_co),sub(it[_it]-co[_co]){}friend bool operator < (price a,price b){return a.sub>b.sub;}
};priority_queue<price> Q;int main(){ cin>>n>>t;for(int i=0;i<n;i++)cin>>it[i];sort(it,it+n);for(int i=0;i<n;i++)cin>>co[i]; sort(co,co+n);for(int i=0;i<n;i++)Q.push(price(i,n-1));int num = 0;while(t>=0&&!Q.empty()){price now = Q.top();if(t<now.sub)break;t -= now.sub;num ++;Q.pop();if(now.coIdx>0)Q.push(price(now.itIdx,now.coIdx-1));}printf("%d %d\n",num,t);return 0;
}第三次结果
相关文章：
erlang supervisor simple_one_for_one实例
http://www.cnblogs.com/little-ant/p/3196201.html simple_one_for_one vs one_for_one: 相同点： 这种Restart Strategy和one_for_one基本相同(即当一个child process挂掉后，仅仅重启该child process 而不影响其他child process)。 异同点： …
sql isnull函数的使用(转载)
sql isnull函数的使用 ISNULL 使用指定的替换值替换 NULL。 语法 ISNULL ( check_expression , replacement_value ) 参数 check_expression 将被检查是否为 NULL的表达式。check_expression 可以是任何类型的。 replacement_value 在 check_expression 为 NULL时将返回的表达…
Error creating bean with name 'defaultHandlerMapping' defined in ServletContext resource
未解决转载于:https://www.cnblogs.com/hqsbrx/p/9969449.html
priority_queue 结构体的优先级设置
目标：使用结构体Node类型的优先队列，让其按照我们希望的顺序进行排序。 预备知识：会结构体的定义，和结构体类型的优先队列的定义，知道优先队列默认是最大堆排序(即top()得到的是最大的元素) 要做的事：在结…
PNG透明兼容IE6的几种方法
png透明针对IE6一直是件挺麻烦的事情，使用的方法也是各有不同，大多的原理是用IE的滤镜来解决的。 语法：filter : progid:DXImageTransform.Microsoft.AlphaImageLoader ( enabledbEnabled , sizingMethodsSize , srcsURL ) enabled : 可选项。…
ntohs的一个简单实现(将网络流中用两个字节16进制表示的资源数(如DNS)和长度转换为整形)...
我们知道在由于大端机和小端机导致网络字节序和主机序有可能是有差异的，我们可以使用系统的ntohs,ntohl,htons和htonl这些处理函数进行转换，下面是我写的一个关于ntohs在处理小端机字节序转换的函数的简单实现. 思想大致如下: 用u_int16_t的2字节16位的整…
循环获取结构体中的健名与值的实现
为什么80%的码农都做不了架构师？>>> type Person struct {Name stringAge int }func main() {a : &Person{"Name", 1}v : reflect.ValueOf(a).Elem() //a需要是引用k : v.Type()for i : 0; i < v.NumField(); i {key : k.Field(i)…
PAT（甲级）2020年春季考试 7-4 Replacement Selection
这种复杂的模拟题，对于我这种菜鸡，只能是根据自己的理解，去把题目给演示出来，然后结合测试用例，一点一点debug打印输出，的确耗时，所以考试要是遇到就放最后吧。 把这题做出来，我的一…
On/Off FlipSwitch 按钮
https://proto.io/freebies/onoff/转载于:https://www.cnblogs.com/ElvinLong/p/4253665.html
P1541 乌龟棋 题解(洛谷,动态规划递推)
题目:P1541 乌龟棋 感谢大神的题解(他的写的特别好) 写一下我对他的代码的理解吧(哎,蒟蒻就这能这样...) 代码: #include<bits/stdc.h> #define ll long long using namespace std; ll num[350100]; ll p[5]; ll f[41][41][41][41]; int main() {ios::sync_with_stdio(fa…
asp.net 操作excel的实现代码
http://www.cnblogs.com/fywh/archive/2010/01/25/1655864.html转载于:https://www.cnblogs.com/modernsky2003/archive/2010/02/26/1673925.html
PAT（甲级）2020年春季考试 7-2 The Judger
这道题在模拟过程类型题种算友好的，很平铺直叙，主要就是hash的应用。 有两个小点： 1. 怎样快速求两个未知大小的整数a和b的差值(>0) abs(a,b) 2. 如果某一轮有不止一个人淘汰，应该输出 Round #1: 3 is out. Round #1: 4 …
C++_volatile限定修饰符 Pair类型
Volatile限定修饰符 当一个对象的值可能会在编译器的控制或检测之外被改变时，例如一个被系统时间更改的变量，那么这个变量就应该声明成volatile。 其主要作用是提示编译器，该对象的值可能在编译器未检测到的情况下被改变。因此编译器执行的某…
FWFT FIFO读操作注意
FWFT：First Word Fall Through的缩写，好像是Xilinx的说法，Altera对应的概念是Show-ahead synchronous(SASO)。即数据在rdreq有效之前就有效了，rdreq作为一个应答(ACK)。 需要注意的是当rdreq连续时，容易多读一个数据…
iOS图像识别
iOS通过摄像头动态识别图像 前言： 目前的计算机图像识别，透过现象看本质，主要分为两大类: 基于规则运算的图像识别，例如颜色形状等模板匹配方法基于统计的图像识别。例如机器学习ML，神经网络等人工智能方法**区别&…
PAT（甲级）2019年冬季考试 7-4 Cartesian Tree
这道题利用的是最小堆和中序排序的属性：只要知道根节点，就能得出哪些属于左子树，哪些属于右子树。 开始我一直报段错误，经过筛查，发现是创建树的函数忘记写返回语句 return root. AC代码 #include<cstdio> #i…
C#操作excel(多种方法比较)
我们在做excel资料的时候，通常有以下方法。 一.导入导出excel常用方法： 1.用查询表的方式查询并show在数据集控件上。 代码 publicstaticstringstrCon "Provider Microsoft.Jet.OLEDB.4.0 ; Data Source C:\\08.xls;Extended PropertiesExcel 8.0&…
383. Ransom Note/691. Stickers to Spell Word-- String, Map, back tracking-- 未完待续
383 easy 题，就是建立字母的hash 表 看第一个String 是否能被第二个String 所构建 canConstruct("aa", "aab") -> true 统计 第二个参数中每个字母的频率，可以用一个int[256] 建立hashmap, 然后统计 第一个String 中字母出现的…
Centos 修改时间地区及NTP同步北京时间
在我们使用CentOS系统的时候，也许时区经常会出现问题，有时候改完之后还是会出错，下面我们就来学习一种方法来改变这个状况。如果没有安装，而你使用的是 CentOS系统 那使用命令 yum install ntp 然后：ntpdate us.pool.n…
PAT（甲级）2019年冬季考试 7-2 Block Reversing
这题是做过的，B1025，我还总结过，果然早晚复相逢，只改了一点点，见1025 反转链表。 点睛之笔是结构体数组的哈希，地址既做下标，又有实际含义，妙啊。 node[add].add add; 当时应该是…
题目1444：More is better
时间限制：3 秒 内存限制：100 兆 特殊判题：否 提交：1362 解决：640 题目描述：Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the bette…
COMP 0137 Machine Vision
COMP 0137作业代做、Python实验作业代写、代做Python语言程序作业、代写Machine Vision作业COMP 0137 Machine Vision: Homework #1Due 19th November 2018 at 23:55pmWorth 10% of your overall gradeSubmit online, through MoodleFor this homework, we’ll revisit the pra…
windows mobile shell API
SHSetNavBarText 设置NavBar 文本信息 SHDoneButton 设置右上角button为关闭，还是最小化。 SHFullScreen 全屏，显示隐藏taskbar 软键盘button 开始图标 SHInitDialog 实例化对话框 SHInitDialogFlags 设置dialog参数…
PAT（甲级）2019年秋季考试 7-3 Postfix Expression
只在编译原理学过一点后序表达式，我把这题当作普通的二叉树遍历，事实上也的确如此。我注意到“-”这个符号不一样，别的都是后序遍历，但是遇到这个负号/减号就变成了先序。 于是我对负号做特判，遇到值为负号就改后序为…
（翻译）LearnVSXNow! #6 - 创建我们第一个工具集 - 序幕
在前面的文章中,我们在向导的帮助下创建了一些小的VSPackages。在第五讲中我们整理了VSX的一些思路和概念，深入VSPackages 了解了packages如何工作以及服务的机制。在这篇文章中我们继续向前。 本文我们开始创建一个工具集来帮助我们创建容易编写和理解的代码。我计…
Spring事务管理的底层逻辑—源码解析
本文代码为spring 5.1.2spring是如何控制事务的提交和回滚 加上Transactional注解之后，Spring可以启到事务控制的功能了，再正式执行方法前它会做一些操作，我们来看看 首先进入CglibAopProxy.class的intercept方法或者JdkDynamicAopProxy.clas…
[codevs 1913] 数字梯形问题
[codevs 1913] 数字梯形问题 题解： 本题就是加强版的 [codevs 1033] 蚯蚓的游戏问题。分别针对三个规则建图、运行最小费用最大流。规则1：从梯形的顶至底的m条路径互不相交。分析：因为要互不相交，所以每个点只能走一次，…
PAT（甲级）2019年秋季考试 7-2 Merging Linked Lists
又是老朋友链表输出题，依然采用哈希静态存储，但是这题稍复杂的是，有两条链表，但是我们可以默认link1>link2，然后让link2上的节点接着link1后面编号，并且注意link2是倒序输出的。 输出时有几个关键点&am…
Flash/Flex学习笔记(4)：如何打开网页及Get/Post数据
flash终究只是客户端技术，所以很多时候还是需要与服务端技术(比如asp,asp.net,jsp,php之类)进行数据交互的，下面的代码演示了如何在flash中打开网页，以及用GET/POST二种方式向服务端发送数据//按下按钮，打开网页 btnOpen.addEvent…
【Mood 19】DailyBuild 2月
2月1号 仿美团loading时小人奔跑动画 HTML5定稿了，为什么原生App世界将被颠覆？ -----HTML5一改过去卡顿不兼容的毛病，在硬件升级以及苹果谷歌策略变化的背景下，让自己的优势相对于原生开发更加明显起来： 对开发者的“跨…