2017Nowcoder Girl初赛重现赛

呃呃呃练练手看看题。。。。去打个酱油

链接：https://ac.nowcoder.com/acm/contest/315/A
来源：牛客网

题目描述

如果一个整数x是某个整数的平方, 我们就把整数x称为平方数。

妞妞最喜欢的数字就是平方数, 妞妞现在给你一个N, 妞妞希望你能帮助她找出不大于N的最大的平方数。

输入描述:

输入包括一行, 包括一个正整数N(1 <= N <= 10^9), 表示妞妞给的数字N。

输出描述:

输出一个整数, 即不大于N的最大的平方数。

示例1

输入

复制

10

输出

复制

9

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
    int n ;
    scanf(\"%d\", &n);
    int gg = sqrt(n);
    printf(\"%d\\n\",gg * gg);
    return 0;
}

链接：https://ac.nowcoder.com/acm/contest/315/D
来源：牛客网

妞妞参加完Google Girl Hackathon之后,打车回到了牛家庄。

妞妞需要支付给出租车司机车费s元。妞妞身上一共有n个硬币，第i个硬币价值为p[i]元。

妞妞想选择尽量多的硬币，使其总价值足以支付s元车费(即大于等于s)。

但是如果从妞妞支付的这些硬币中移除一个或者多个硬币，剩下的硬币总价值还是足以支付车费的话，出租车司机是不会接受的。例如: 妞妞使用价值为2，5，7的硬币去支付s=11的车费,出租车司机是不会接受的，因为价值为2这个硬币是可以移除的。

妞妞希望能选取最大数量的硬币，使其总价值足以支付车费并且出租车司机能接受。

妞妞希望你能帮她计算最多可以支付多少个硬币。

输入描述:

输入包括两行, 第一行包括两个正整数n和s(1 <= n <= 10, 1 <= s <= 1000), 表示妞妞的硬币个数和需要支付的车费。
第二行包括n个正整数p[i] (1 <= p[i] <= 100)，表示第i个硬币的价值。
保证妞妞的n个硬币价值总和是大于等于s。

输出描述:

输出一个整数, 表示妞妞最多可以支付的硬币个数。

示例1

输入

复制

5 9
4 1 3 5 4

输出

复制

3

代码：

#include<bits/stdc++.h>
using namespace std;
int coin[15], s , n;
int total = 0;
void DFS(int id , int sum, int ans)
{
	if(sum >= s) //应该说第一步 已经大于的时候就应该结束 
	{
		total = max(ans , total);
		return;
	}
	if(id > n )
		return; 
	DFS(id + 1, sum + coin[id],ans + 1);
	DFS(id + 1,sum , ans);	
}
bool cmp( int a , int b){
	return a > b;
}
int main()
{
	scanf(\"%d %d\",&n, &s);
	for(int i = 1; i <= n ; i ++)
		scanf(\"%d\",&coin[i]);
	
	sort(coin + 1, coin + 1 + n,cmp);//从大到小排序 
	DFS(1, 0, 0);
	printf(\"%d\\n\",total);
	return 0;
}