记录刷题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;}