去哪儿。编程第二题,怎么做啊,求解答。

题目意思是,输入n个int数,[0,n-2]表示n-1个酒店的每晚价格,第[n-1]个元素是你拥有的钱。
要求输出,能住最少的天数,且钱必须刚好花完。
若不存在匹配情况,则返回-1.
#去哪儿#
全部评论
参考博客 http://blog.csdn.net/jiejinquanil/article/details/52684449
点赞 回复 分享
发布于 2016-09-27 21:13
可以搜一下“完全背包”看一看
点赞 回复 分享
发布于 2016-09-27 15:24
为什么是最少天数而不是最多天数。。
点赞 回复 分享
发布于 2016-09-27 15:25
用dfs过了。。
点赞 回复 分享
发布于 2016-09-27 15:27
http://blog.csdn.net/kangroger/article/details/36036101,,,这个你懂了,就会做去哪网的题了
点赞 回复 分享
发布于 2016-09-27 15:32
是个动态规划问题,只用贪心可以过83%
点赞 回复 分享
发布于 2016-09-27 15:38
这不就是一个数组中最少数之和等于最后一个元素的问题吗!
点赞 回复 分享
发布于 2016-09-27 15:42
完全背包 HDU1114,有很多题解,百度一下。
点赞 回复 分享
发布于 2016-09-27 15:56
67%没办法完美
点赞 回复 分享
发布于 2016-09-27 15:57
package qunar; import java.util.Scanner; public class Main2 { static int rel =9999; public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); String s; while(in.hasNext()){ s = in.nextLine(); rel = 9999; gs(s); if(rel != 9999){ System.out.println(rel); }else{ System.out.println("-1"); } } } public static void gs(String s){ String[] ar = s.split(" "); int n = ar.length; int[] arr = new int[n]; for(int i=0;i<n;i++){ arr[i] = Integer.valueOf(ar[i]); } dp(arr,n-2,arr[n-1],0); } public static void dp(int[] arr,int now,int money,int day){ if(money < 0){ return; } if(money == 0){ if(day < rel){ rel = day; return ; } } if(money%arr[now] == 0){ if(money/arr[now] < rel){ rel = money/arr[now]+day; return; } }else{ for(int i=now;i>=0;i--){ if(money>=arr[i]){ dp(arr,i,money-arr[i],day+1); } } } } } 有一些多余的地方
点赞 回复 分享
发布于 2016-09-27 16:06
可不可以住重复的酒店
点赞 回复 分享
发布于 2016-09-27 16:16
可以使用递归来解决,AC83%
点赞 回复 分享
发布于 2016-09-27 16:33
楼主收到面试通知了吗,据说当天就给,第二天就面
点赞 回复 分享
发布于 2016-09-27 17:48
找钱问题
点赞 回复 分享
发布于 2016-09-27 18:42
有兄弟收到面试通知没
点赞 回复 分享
发布于 2016-09-27 18:55
确实是 找钱问题,参考了下,感觉现在应该没问题,好像还不用排序。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; vector<int> v; int money; while (cin >> n) { v.push_back(n); } money = v[v.size() - 1]; v.pop_back(); //sort(v.begin(), v.end()); int length = v.size(); int *days = new int[money + 1]; int *value = new int[money + 1]; days[0] = 0; for (int i = 1; i <= money; i++) { int min = i; int used = 0; for (int j = 0; j < length; j++) { if (i >=v[j]) { if (days[i - v[j]] + 1 <= min && (i == v[j] || value[i - v[j]] != 0)) { min = days[i - v[j]] + 1; used = v[j]; } } } days[i] = min; value[i] = used; } if (value[money] == 0) cout << -1 << endl; else cout << days[money] << endl; //system("pause"); return 0; }
点赞 回复 分享
发布于 2016-09-27 21:24
贪心算法,AC83%: #include <iostream> #include <vector> #include <algorithm>   #include <string> #include <sstream> using namespace std; bool SortByM1(const int &v1, const int &v2)  { return v1 > v2; } //main int main(){ vector<int> vecPrice; int nMoney; int nTemp; int nCount = 0; int nCurrentNumber = 0; string strLine;  getline(cin, strLine);  stringstream iss(strLine);  for (int i; iss >> i; vecPrice.push_back(i)); nMoney = vecPrice.back(); vecPrice.pop_back(); //降序排列 sort(vecPrice.begin(), vecPrice.end(), SortByM1); vector<int>::const_iterator iter = vecPrice.begin(); for (; iter != vecPrice.end(); iter++){ nCurrentNumber = *iter; while (nCurrentNumber<=nMoney) //贪心算法 { nCount++; nMoney -= nCurrentNumber; } if (nMoney==0) { break; } } if (nCount==0||nMoney>0) cout << "-1" << endl; else    cout << nCount << endl; }
点赞 回复 分享
发布于 2016-09-27 21:37
贪心AC了
点赞 回复 分享
发布于 2016-09-27 21:40
参考大神的,改了改 贪心或者说是dfs,只要不超时,应该全AC #include<iostream> #include<vector> #include<algorithm> using namespace std; int res = 0x7fffffff; void dfs(vector<int> v, int money, int k, int n) { if (money == 0) { res = res>k?k:res; return; } if (money < 0 || n < 0 || k > res) return; for (int i = money / v[n]; i >= 0; i--) dfs(v, money - i * v[n], k + i, n - 1); } int main() { int n; vector<int> v; int money; while (cin >> n) { v.push_back(n); } money = v[v.size() - 1]; v.pop_back(); sort(v.begin(), v.end()); int days = 0; dfs(v, money, 0, v.size()-1); if (res == 0x7fffffff) res = -1; cout << res; //system("pause"); return 0; }
点赞 回复 分享
发布于 2016-09-28 19:26
public class Main4 { static Integer res = Integer.MAX_VALUE; public static void main(String[] args) { int[] n = {1,2,3,4,6,2,5,6}; ArrayList<Integer> list = new ArrayList<>(); f(n,0,0,0); System.out.println(res); } private static void f(int[] n, int idx, int tmp, int tmpr){ if(tmp == n[n.length - 1] && tmpr < res){ res = tmpr; } if(tmp > n[n.length - 1] || idx == n.length - 2){ return; } if(idx + 1 < n.length - 1){ f(n,idx + 1, tmp, tmpr); f(n,idx + 1, tmp += n[idx], tmpr + 1); } } }
点赞 回复 分享
发布于 2016-09-29 19:09

相关推荐

11-12 15:08
已编辑
长江大学 算法工程师
3年前的秋招季,原来只是一个新手教程罢了。2个月之前,我,一个9本华五硕,手上一个Offer都没有。从来没想到会遇到这样的场面,大环境退化了,自己的价值也没有在这段经历中有所提升。实验室里同届的人也都至少面的很顺,有个保底,而我还在挣扎求生。但结果只是惨淡,算不上完败:上周五我收到了小红书的oc,同时最近也接到了华为的保温电话,这标志着互联网公司的沟通基本都有了个结果。是时候该回顾一下过去的心得了,我想以一位网友给我的一份回复,一个教训作为切入点。一个教训也就在秋招最困难的这段时间,我发帖吐槽了一位让我感觉不舒服的面试官,于是受到了一位“工作两年多的网友”的教训。虽然他已经删除这段话,但我很在...
牛客73841773号:怀着复杂的心情读了好几遍,丝毫没感受到作者“读书人的傲慢”,反而,透过这段逻辑清晰、有理有据的文字,我感受到了一种读书人特有的温厚的力量,这显然是名校熏陶和个人修养综合作用的结果。这种力量,让我想起过去一百多年里许多名校学子所展现出的,自强不息的进取精神,通透达观的处世心态,悲智双运的人文关怀。这位作者,你清醒的智慧、清晰的远见、不卑不亢的态度和公正的自我认知,一定会让你在不久的将来作出正确的选择,过上幸福的人生。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务