记录刷题QAQ
一、第一次，第二次，成交！
题目描述
因为奶牛们的节食运动给 FJ 余下了一大批干草无法处理，所以他准备要开一个拍卖会去出售他的干草。
他有 n n n 批干草（每批大约 100 100 100 捆）。他的客户有 m m m 个，都是和他相邻的农夫。第 i i i 名农夫会告诉 FJ 他会为 FJ 的每批干草付 p i p_i pi 的钱。每个农夫都想买（也只想买）FJ 的一批草料。
为了确保农夫们不会互相嫉妒，所以 FJ 决定要以一个固定的价格出售他的草料。每一个出价比 FJ 的要价要高的农夫将会买到草料，余下的将会被拒绝购买。
请你帮助 FJ 找出能让他赚到最多的钱的最低的单批草料的售价。
输入格式
第一行：两个被空格隔开的整数， n n n 和 m m m。
第二行到第 m + 1 m+1 m+1 行：第 i + 1 i+1 i+1 行只包含一个整数： p i p_i pi。
输出格式
共一行，包含由空格隔开的两个整数：FJ 能出的每批草料的最低价格，以及他能赚到的最多的钱。
样例 #1
样例输入 #1
5 4
2
8
10
7
样例输出 #1
7 21
提示
FJ 有 5 5 5 批草料， 4 4 4 个农夫想要购买。他们出价分别为：每批草料为 2 2 2， 8 8 8， 10 10 10 和 7 7 7。
FJ 应该把价格设定为 7 7 7，这样会有 3 3 3 个农夫会付钱买草料，FJ 自己会挣到 21 21 21 的钱。
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1000 1\leq n\leq 1000 1≤n≤1000， 1 ≤ m ≤ 1000 1\leq m\leq 1000 1≤m≤1000， 1 ≤ p i ≤ 1 , 000 , 000 1\leq p_i\leq 1,000,000 1≤pi≤1,000,000。
代码如下：
#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int main()
{
int n, m;//n是 干草的批次，m是客户个数
scanf("%d%d",&n,&m);
int num[m];
int max = 0;
for(int i = 0;i < m;i++)
{
scanf("%d",&num[i]);
}
for(int i = 0;i < m;i++)
{
for(int j = i;j < m;j++)
{
if(num[j] < num[i])
{
num[j] = num[j] + num[i];
num[i] = num[j] - num[i];
num[j] = num[j] - num[i];
}
}
}
int price = 0;
for(int i = 0;i < m;i++)
{
int NUM = m;
int sum = num[i] *(m-i);
if(sum > max){
price = num[i];
max = sum;
}
}
if(n < max/price) max = price*n;
printf("%d %d\n",price,max);
return 0;
}
二、[USACO07OCT]Bessie’s Secret Pasture S
题目背景
背景就是描述，描述就是背景。
题目描述
Farmmer John最近收割了几乎无限多块牧草，将它们堆放在空地上。这些牧草都是正方形的，而且都有非负整数长度的边长（当然有0）。一天它的奶牛Bessie发现了这些美味的牧草，于是希望把它们种在自己的秘密牧场上。他总将草皮分割成1*1的小块，以放入他牧场上的N个格子中。
Bessie感兴趣的是，她若选取四块会有多少种不同方法。如果N=4，那么她就有5种不同分发：(1,1,1,1),(2,0,0,0),(0,2,0,0),(0,0,2,0),(0,0,0,2)，括号内数表示边长。注意这里不讲究顺序，如(1,2,3,4)与(4,3,2,1)是两种不同方法。
输入格式
仅一行，一个整数N。
输出格式
同样为一行，包含一个整数，为方案总数。
样例 #1
样例输入 #1
4
样例输出 #1
5
提示
对于100%的数据，1<=N<=10000。
代码如下：
#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int sqr[101];
int app[20001];
int main()
{
int n,f,ans=0;
scanf("%d",&n);
f=sqrt(n);
for(int i=0; i<=f; i++) {
sqr[i]=i*i;
app[i*i]=1;
}
for(int i=0; i<=f; i++) {
for(int j=0; j<=f; j++) {
if(sqr[i]+sqr[j]>n) break;
for(int k=0; k<=f; k++) {
if(sqr[i]+sqr[j]+sqr[k]>n) break;
if(app[n-sqr[i]-sqr[j]-sqr[k]]) {
ans++;
}
}
}
}
printf("%d",ans);
return 0;
}
三、[NOIP2015 普及组] 金币
题目背景
NOIP2015 普及组 T1
题目描述
国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 n n n 天每天收到 n n n 枚金币后，骑士会在之后的连续 n + 1 n+1 n+1 天里，每天收到 n + 1 n+1 n+1 枚金币。
请计算在前 k k k 天里，骑士一共获得了多少金币。
输入格式
一个正整数 k k k，表示发放金币的天数。
输出格式
一个正整数，即骑士收到的金币数。
样例 #1
样例输入 #1
6
样例输出 #1
14
样例 #2
样例输入 #2
1000
样例输出 #2
29820
提示
【样例 1 说明】
骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 1 + 2 + 2 + 3 + 3 + 3 = 14 1+2+2+3+3+3=14 1+2+2+3+3+3=14 枚金币。
对于 100 % 100\% 100% 的数据， 1 ≤ k ≤ 1 0 4 1\le k\le 10^4 1≤k≤104。
代码如下：
#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int sqr[101];
int app[20001];
int main()
{
int k;//k天
scanf("%d",&k);
int num = 0;
int n = 0;
while(k > num)
{
n++;
num = (n+1)*n/2;
}
long long sum = 0;
if(num != k){
for(int i = 1;i < n;i++)
{
sum = sum + i*i;
}
int m = (n-1)*n/2;
sum = (k - m)*n + sum;
printf("%lld\n",sum);
}
else if(num == k)
{
for(int i = 1;i <= n;i++)
{
sum = sum + i*i;
}
printf("%lld\n",sum);
}
return 0;
}
四、[USACO07DEC]Bookshelf B
题目描述
Farmer John最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。
所有 N ( 1 ≤ N ≤ 20 , 000 ) N(1 \le N \le 20,000) N(1≤N≤20,000) 头奶牛都有一个确定的身高 H i ( 1 ≤ H i ≤ 10 , 000 ) H_i(1 \le H_i \le 10,000) Hi(1≤Hi≤10,000)。设所有奶牛身高的和为S。书架的高度为B，并且保证 1 ≤ B ≤ S < 2 , 000 , 000 , 007 1 \le B \le S < 2,000,000,007 1≤B≤S<2,000,000,007。
为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。
显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。
输入格式
- 第 1 1 1 行: 2 个用空格隔开的整数： N N N 和 B B B；
- 第 2 … N + 1 2\dots N+1 2…N+1 行: 第 i + 1 i+1 i+1 行是 1 1 1 个整数： H i H_i Hi。
输出格式
- 第 1 1 1 行: 输出 1 1 1 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部
样例 #1
样例输入 #1
6 40
6
18
11
13
19
11
样例输出 #1
3
提示
输入说明:
一共有 6 6 6 头奶牛，书架的高度为 40 40 40，奶牛们的身高在 6 … 19 6\dots19 6…19之间。
输出说明:
一种只用 3 3 3 头奶牛就达到高度 40 40 40 的方法： 18 + 11 + 13 18+11+13 18+11+13。当然还有其他方法，在此不一一列出了。
代码如下：
#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int sqr[101];
int app[20001];
int main()
{
int n;
long long b;
//n是奶牛的数量，b 是书架的高度
scanf("%d%lld",&n,&b);
int num[n];
for(int i = 0;i < n;i++)
{
scanf("%d",&num[i]);
}
for(int i = 0;i < n;i++)
{
for(int j = i;j < n;j++)
{
if(num[j] > num[i])
{
num[j] = num[i] + num[j];
num[i] = num[j] - num[i];
num[j] = num[j] - num[i];
}
}
}
int m = 0;
long long sum = 0;
while(sum < b)
{
sum = sum + num[m];
m++;
}
printf("%d",m);
return 0;
}
五、东南西北
题目描述
给出起点和终点的坐标及接下来T个时刻的风向(东南西北)，每次可以选择顺风偏移1个单位或者停在原地。求到达终点的最少时间。
如果无法偏移至终点，输出“-1”。
输入格式
第一行两个正整数x1,y1，表示小明所在位置。
第二行两个正整数x2,y2，表示小明想去的位置。
第三行一个整数T，表示T个时刻。
第四至第N+3行，每行一个字符，表示风向，即东南西北的英文单词的首字母。
输出格式
最少走多少步。
样例 #1
样例输入 #1
1 1
2 2
5
E
N
W
W
N
样例输出 #1
2
样例 #2
样例输入 #2
1 1
2 2
1
W
样例输出 #2
-1
样例 #3
样例输入 #3
1 1
2 2
3
W
W
W
样例输出 #3
-1
提示
样例1：向东走一步，向北走一步。
样例2、3：无法到达。
1<=T<=50
东：East
南：South
西：West
北：North
代码如下：
#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int main()
{
int x1,y1,x2,y2,t,sum=0;
scanf("%d%d",&x1,&y1);
scanf("%d%d",&x2,&y2);
scanf("%d",&t);
int a=abs(x1-x2),b=abs(y1-y2);//需要走的距离
char a1=x1>x2?'W':'E',b1=y1>y2?'S':'N'/*方向*/,wind[t+1];
for(int i = 1;i <= t;i++)
{
scanf("%s",&wind[i]);
}
for(int i=1;i<=t;i++)
{
if(a!=0&&a1==wind[i])
{
a--;
sum++;
}
else if(b!=0&&b1==wind[i])
{
b--;
sum++;
}//在目标距离已走完的情况下不要多走，浪费时间
}
if(a!=0||b!=0) printf("-1");//没走完
else printf("%d",sum);
return 0;
}