记录刷题QAQ

一、第一次，第二次，成交！

题目描述

因为奶牛们的节食运动给 FJ 余下了一大批干草无法处理，所以他准备要开一个拍卖会去出售他的干草。

他有 nnn 批干草（每批大约 100100100 捆）。他的客户有 mmm 个，都是和他相邻的农夫。第 iii 名农夫会告诉 FJ 他会为 FJ 的每批干草付 pip_ipi​ 的钱。每个农夫都想买（也只想买）FJ 的一批草料。

为了确保农夫们不会互相嫉妒，所以 FJ 决定要以一个固定的价格出售他的草料。每一个出价比 FJ 的要价要高的农夫将会买到草料，余下的将会被拒绝购买。

请你帮助 FJ 找出能让他赚到最多的钱的最低的单批草料的售价。

输入格式

第一行：两个被空格隔开的整数，nnn 和 mmm。

第二行到第 m+1m+1m+1 行：第 i+1i+1i+1 行只包含一个整数：pip_ipi​。

输出格式

共一行，包含由空格隔开的两个整数：FJ 能出的每批草料的最低价格，以及他能赚到的最多的钱。

样例 #1

样例输入 #1

5 428107

样例输出 #1

7 21

提示

FJ 有 555 批草料，444 个农夫想要购买。他们出价分别为：每批草料为 222，888，101010 和 777。

FJ 应该把价格设定为 777，这样会有 333 个农夫会付钱买草料，FJ 自己会挣到 212121 的钱。

对于 100%100\%100% 的数据，1≤n≤10001\leq n\leq 10001≤n≤1000，1≤m≤10001\leq m\leq 10001≤m≤1000，1≤pi≤1,000,0001\leq p_i\leq 1,000,0001≤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;}

三、[NOIP 普及组] 金币

题目背景

NOIP 普及组 T1

题目描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 nnn 天每天收到 nnn 枚金币后，骑士会在之后的连续 n+1n+1n+1 天里，每天收到 n+1n+1n+1 枚金币。

请计算在前 kkk 天里，骑士一共获得了多少金币。

输入格式

一个正整数 kkk，表示发放金币的天数。

输出格式

一个正整数，即骑士收到的金币数。

样例 #1

样例输入 #1

6

样例输出 #1

14

样例 #2

样例输入 #2

1000

样例输出 #2

29820

提示

【样例 1 说明】

骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 1+2+2+3+3+3=141+2+2+3+3+3=141+2+2+3+3+3=14 枚金币。

对于 100%100\%100% 的数据，1≤k≤1041\le k\le 10^41≤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) 头奶牛都有一个确定的身高 Hi(1≤Hi≤10,000)H_i(1 \le H_i \le 10,000)Hi​(1≤Hi​≤10,000)。设所有奶牛身高的和为S。书架的高度为B，并且保证 1≤B≤S<2,000,000,0071 \le B \le S < 2,000,000,0071≤B≤S<2,000,000,007。

为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。

显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

输入格式

第 111 行: 2 个用空格隔开的整数：NNN 和 BBB；第 2…N+12\dots N+12…N+1 行: 第 i+1i+1i+1 行是 111 个整数：HiH_iHi​。

输出格式

第 111 行: 输出 111 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部

样例 #1

样例输入 #1

6 4061811131911

样例输出 #1

3

提示

输入说明:

一共有 666 头奶牛，书架的高度为 404040，奶牛们的身高在 6…196\dots196…19之间。

输出说明:

一种只用 333 头奶牛就达到高度 404040 的方法：18+11+1318+11+1318+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 12 25ENWWN

样例输出 #1

2

样例 #2

样例输入 #2

1 12 21W

样例输出 #2

-1

样例 #3

样例输入 #3

1 12 23WWW

样例输出 #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;}