hihocoder-编程练习赛-34
题目1：
“共同富裕”
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个数组A1, A2, ... AN，每次操作可以从中选定一个元素Ai，把除了Ai之外的所有元素都加1。
问最少几次操作可以实现“共同富裕”，即数组中所有元素都相等。
例如对于[1, 1, 1, 2, 3]经过3步:[1, 1, 1, 2, 3] -> [2, 2, 2, 3, 3] -> [3, 3, 3, 3, 4] -> [4, 4, 4, 4, 4]。
输入
第一行包含一个整数N。(1 ≤ N ≤ 100000)
以下N行包含N个整数A1, A2, ... AN。 (1 ≤ Ai ≤ 100000)
输出
最小的操作数
- 样例输入
-
5 1 1 1 2 3
- 样例输出
-
3
使用贪心算法， 对数组进行sort之后，按照每一个元素与最小元素的累计差，就是ans。
#include <cstdio>
#include <cstdlib>
const int MAXN = 100000 + 10;
int num[MAXN];
int cmp(const void *a, const void *b){
return (*(int *)a - *(int *)b);
}
int main(){
int n;
while(scanf("%d", &n) != EOF){
for(int i=0; i<n; ++i){
scanf("%d", &num[i]);
}
qsort(num, n, sizeof(num[0]), cmp);
long long ans = 0;
for(int i=n-1; i>0; --i){
ans += num[i] - num[0];
}
printf("%lld
", ans );
}
return 0;
}
题目2 : 股票价格3
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi最近在关注股票，为了计算股票可能的盈利，他获取了一只股票最近N天的价格A1~AN。
小Hi想知道，对于第i天的股票价格Ai，几天之后股价会第一次超过Ai。
假设A=[69, 73, 68, 81, 82]，则对于A1=69，1天之后的股票价格就超过了A1；对于A2=73，则是2天之后股票价格才超过A2。
输入
第一行包含一个整数N。
以下N行每行包含一个整数Ai。
对于50%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000, 1 ≤ Ai ≤ 1000000
输出
输出N行，其中第i行代表对于第i天的股票价格Ai，几天之后股价会第一次超过Ai。
如果Ai+1~AN之内没有超过Ai，输出-1。
- 样例输入
-
5 69 73 68 81 82
- 样例输出
-
1 2 1 1 -1
同样是贪心的思想，
从后面开始向前扫，用stack来保存当前的最近最大num就行了。
#include <cstdio>
#include <cstdlib>
const int MAXN = 100000 + 10;
int num[MAXN], stack[MAXN], ans[MAXN], stack_id[MAXN];
int main(){
int n, top;
while(scanf("%d", &n) != EOF){
for(int i=0; i<n; ++i){
scanf("%d", &num[i]);
}
top = 0;
stack[ top ] = num[n-1];
stack_id[ top++ ] = n-1;
ans[ n-1 ] = -1;
for(int i=n-2; i>=0; --i){
if( num[i] < stack[top-1] ){
ans[ i ] = stack_id[ top-1 ] - i;
}else{
while(top>0 && num[i] >= stack[top-1]){
--top;
}
if(top == 0){
ans[ i ] = -1;
}else{
ans[ i ] = stack_id[ top-1 ] - i;
}
}
stack[ top ] = num[i];
stack_id[ top++ ] = i;
}
for(int i=0; i<n; ++i){
printf("%d
", ans[i] );
}
}
return 0;
}