狐进行了一次黑客马拉松大赛，全公司一共分为了N个组，每组一个房间排成一排开始比赛，比赛结束后没有公布成绩，但是每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩，比赛结束之后要发奖金，以1w为单位，每个组都至少会发1w的奖金，另外，如果一个组发现自己的奖金没有高于比自己成绩低的组发的奖金，就会不满意，作为比赛的组织方，根据成绩计算出至少需要发多少奖金才能让所有的组满意。
[编程题]发奖金
- 热度指数：7171 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
每组数据先输入N，然后N行输入N个正整数，每个数表示每个组的比赛成绩。
输出描述:
输出至少需要多少w的奖金
示例1
输入
10 20 32 12 32 45 11 21 31 41 33
输出
20
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
vector<int>a(n,0);
for(int i=0;i<n;i++)
cin>>a[i];
vector<int>b(n,1);
for(int i=1;i<n;i++)//从前往后
if(a[i]>a[i-1])
b[i]=b[i-1]+1;
for(int i=n-2;i>=0;i--)//从后往前
if(a[i]>a[i+1]&&b[i]<b[i+1]+1)
b[i]=b[i+1]+1;
long sum=0;
for(int i=0;i<n;i++)
sum+=b[i];
cout<<sum<<endl;
}
}
之前做过类似的，就是从前往后来一遍，后面比前面大就++；再从后往前一遍 ，前面比后面大就++
发表于 2016-09-02 20:10:10
回复(4)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int N = scanner.nextInt();
int[] grades = new int[N];
for (int i = 0; i < N; i++) {
grades[i] = scanner.nextInt();
}
int[] bonus = new int[N];
int[] cobonus = new int[N];
bonus[0] = 1;
cobonus[N-1] = 1;
for (int i = 1; i < grades.length; i++) {
if (grades[i] > grades[i-1])
bonus[i] = bonus[i-1] + 1;
else
bonus[i] = 1;
}
for (int i = N-1; i > 0; i--) {
if (grades[i-1] > grades[i])
cobonus[i-1] = cobonus[i] + 1;
else
cobonus[i-1] = 1;
}
int sum = 0;
for (int i = 0; i < N; i++) {
int temp = bonus[i]>cobonus[i]?bonus[i]:cobonus[i];
sum += temp;
}
System.out.println(sum);
}
}
}
从头到尾，从尾到头都来一遍，结果分别存在两个数组里，最后取两个数组中米一个元素较大的一个，相加得到最后结果。
发表于 2016-05-24 21:45:00
回复(3)
dp[i]表示每个组的奖金 一开始都是0(每个组的1万最后加 反正总和是n万)
对每个点i往两边搜索 如果两边都i比高dp[i]=0
否则找到比i低且持续降低的最长长度len此时dp[i] = len - 1; 左右两个方向取最大的
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 3;
int a[maxn], dp[maxn], n;
void solve(int p){//每个点往两边搜索
int pos = p, len = 1;
while(pos+1 < n && a[pos+1] < a[pos]){//右边
pos++; len++;
}
dp[p] = len - 1, len = 1, pos = p;
while(pos-1 >= 0 && a[pos-1] < a[pos]){//左边
pos--; len++;
}
dp[p] = max(dp[p], len - 1);//取左右最大的
}
int main(){
while(scanf("%d", &n) != EOF){
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
memset(dp, 0, sizeof(dp));
int ans = n;
for(int i = 0; i < n; i++) {
solve(i); ans += dp[i];
}
cout<<ans<<endl;
}
}
编辑于 2018-10-31 22:50:44
回复(0)
水题。默认每次发1，如果当前组比前一个组分数高，则发前一组奖金+1；如果当前组比前一组小，直接遍历前面已发的组，每组奖金+1，直到当前组大于等于前一组。
#include <bits/stdc++.h>
using namespace std;
int main(){
for(int N,sum;cin>>N;){
vector<int> score(N,0),bonus(N,1);
for(int i=0;i<N;cin>>score[i++]);
for(int i=1;i<N;++i){
if (score[i] > score[i-1])
bonus[i]=bonus[i-1]+1;
else if (score[i]<score[i-1]){
for(int j=i-1;j>-1;--j){
if (score[j]>score[j+1] && bonus[j]<=bonus[j+1])
++bonus[j];
else break;
}
}
}
for(int i=sum=0;i<N;sum+=bonus[i++]);
cout<<sum<<endl;
}
return 0;
}
发表于 2016-08-23 14:50:16
回复(1)
先说下思路，一开始只是考虑到11,21,32,54,11,22这种情况的，设想的是如果遇到比前一个大的就 加一，如果遇到比前面小的就初始化为1，弄一个数组存这些数，但是如果遇到这种情况就不行了， 例如：11，21，32，54，33，22，11，这样的话，会导致答案错误。 解决办法的是弄两个数组，一个数组按照正常的顺序遍历，另一个数组倒序遍历，然后比较两个数组 的值，取较大的值即可。
import java.util.Scanner; public class SendWard { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner s = new Scanner(System.in); while (s.hasNextInt()) { int n = s.nextInt(); int a[] = new int[n]; int h[] = new int[n]; h[0] = 1; int r[] = new int[n]; int res = 0; r[n - 1] = 1; for (int i = 0; i < n; i++) { a[i] = s.nextInt(); } for (int i = 1; i < n; i++) { if (a[i - 1] < a[i]) { h[i] = h[i - 1] + 1; } else { h[i] = 1; } } for (int i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { r[i] = r[i + 1] + 1; if (r[i] > h[i]) h[i] = r[i]; } else { r[i] = 1; } } for (int i = 0; i < n; i++) { res += h[i]; } System.out.println(res); } } }
发表于 2016-08-08 15:25:09
回复(0)
首先，正序的操作是基本很好想到的：如果比前一个数大，就加一，但是存在连续降序的情况，这时候只需要将正序的操作变相地逆序来一次，即可实现
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
int n;
while(cin >> n) {
int count = n;
vector<int> A;
while (count-- > 0) {
int temp;
cin >> temp;
A.push_back(temp);
}
vector<int> money(n, 1);
for (int i = 1; i < n; i++) {
if (A[i] > A[i - 1]) {
money[i] = money[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (A[i] > A[i + 1] && money[i] <= money[i + 1]) {
money[i] = money[i + 1] + 1;
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += money[i];
}
cout << sum << endl;
}
}
发表于 2017-09-10 17:18:44
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int N;
while(cin>>N){
vector<int> array(N);
for(int i=0;i<N;i++){
cin>>array[i];
}
vector<int> bonus(N);
for(int i=0;i<N;i++) bonus[i]=1;
int money=0;
for(int i=0;i<N;i++){
if(i==0){
if(array[i]>array[i+1]){
bonus[i]=bonus[i+1]+1;
}
}else{
if(i==N-1){
if(array[i]>array[i-1]){
bonus[i]=bonus[i-1]+1;
}
}else{
if(array[i]>array[i-1]&&array[i]>array[i+1]){
bonus[i]=bonus[i-1]>bonus[i+1]? bonus[i-1]+1:bonus[i+1]+1;
}else{
if(array[i]>array[i-1]&&array[i]<=array[i+1])
bonus[i]=bonus[i-1]+1;
if(array[i]<array[i-1]&&array[i]>=array[i+1])
bonus[i]=bonus[i+1]+1;
}
}
}
money+=bonus[i];
}
int x=money;
money=0;
for(int i=N-1;i>=0;i--){
if(i==0){
if(array[i]>array[i+1]){
bonus[i]=bonus[i+1]+1;
}
}else{
if(i==N-1){
if(array[i]>array[i-1]){
bonus[i]=bonus[i-1]+1;
}
}else{
if(array[i]>array[i-1]&&array[i]>array[i+1]){
bonus[i]=bonus[i-1]>bonus[i+1]? bonus[i-1]+1:bonus[i+1]+1;
}else{
if(array[i]>array[i-1]&&array[i]<=array[i+1])
bonus[i]=bonus[i-1]+1;
if(array[i]<array[i-1]&&array[i]>=array[i+1])
bonus[i]=bonus[i+1]+1;
}
}
}
money+=bonus[i];
}
if(x<money)
cout<<money<<endl;
else
cout<<x<<endl;
}
return 0;
}
发表于 2016-08-12 17:12:30
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N,i,j,k;
while(cin>>N){
vector<int> vec;
int n;
for(i=0;i<N&&cin>>n;i++){
vec.push_back(n);
}
int sum=0;
i=0;
while(i<N){
k=1;
for(j=i;j<N-1&&vec[j]>vec[j+1];j++)
k++;
for(;i<=j;i++){
sum+=k;
if(i<N-1&&vec[i]>vec[i+1])
k--;
}
for(;i<N&&i>0&&vec[i-1]<vec[i];i++){
k++;
sum+=k;
}
int l=1;
for(j=i-1;j<N-1&&vec[j]>vec[j+1];j++,l++);
if(l>k)
sum=sum-k+l;
}
cout<<sum<<endl;
}
}
发表于 2016-07-12 15:07:26
回复(0)
#include <iostream>
using namespace std;
int n;
int main(){
while(cin >> n){
int A[n];
for(int i=0; i<n; ++i) cin >> A[i];
int B[n], C[n];
for(int i=0; i<n; ++i){
if(i == 0) B[i] = 1;
else if(A[i] > A[i-1]) B[i] = B[i-1] + 1;
else if(A[i] <= A[i-1]) B[i] = 1;
}
for(int i=n-1; i>=0; --i){
if(i == n-1) C[i] = 1;
else if(A[i] > A[i+1]) C[i] = C[i+1] + 1;
else if(A[i] <= A[i+1]) C[i] = 1;
}
int res = 0;
for(int i=0; i<n; ++i){
res += max(B[i], C[i]);
}
cout << res << endl;
}
return 0;
} 正着来一遍，倒着来一遍，再来一遍取max
发表于 2019-08-12 11:28:24
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{ int N; while(cin>>N) { vector<int> score; vector<int> money(N,0); for(int i=0;i<N;i++) { int t; cin>>t; score.push_back(t); } money[0] = 1; for(int i=0;i<N-1;i++) { if(score[i] < score[i+1]) money[i+1] = money[i] + 1; else if(score[i] > score[i+1]){ money[i+1] = 1; if(money[i] <= money[i+1]) { for(int k=i+1;score[k-1]>score[k]+1 && money[k]+1>money[k-1];k--) money[k-1] = money[k-1]+1; } }else money[i+1] = 1; } int sum = 0; for(int i=0;i<money.size();i++) sum += money[i]; cout<<sum<<endl; } return 0;
}
发表于 2017-11-06 13:40:42
回复(0)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace GetBonus
{
class Program
{
static void Main(string[] args)
{
int N = 0, i, j, pregrade, prebonus, sum;
//输入组数
N = Convert.ToInt32(Console.ReadLine());
while (N != 0)
{
int[] grade = new int[N];
int[] bonus = new int[N];
//依次输入分数
for (i = 0; i < N; i++)
{
grade[i] = Convert.ToInt32(Console.ReadLine());
}
//初始化第一组为1w
bonus[0] = 1;
for (i = 1; i < N; i++)
{
//初始化该组奖金为1w
bonus[i] = 1;
//得到前一组的分数，并得到前一组的奖金
pregrade = grade[(i - 1)];
prebonus = bonus[(i - 1)];
//之前一组分数比该组高但奖金不如该组此时奖金
if ((prebonus <= bonus[i]) && (pregrade > grade[i]))
{
//前一组奖金比当前组加一
bonus[(i - 1)] = bonus[i] + 1;
//之后需将前面的组依次增加奖金
for (j = i - 1; j > 0; j--)
{
if ((bonus[j - 1] <= bonus[j]) && (grade[j - 1] > grade[j]))
{
bonus[(j - 1)] = bonus[j] + 1;
}
}
}
//之前组分数比当前组低
if (pregrade < grade[i])
{
//当前组奖金比之前组多1
bonus[i] = bonus[(i - 1)] + 1;
}
}
sum = bonus.Sum();
Console.WriteLine(sum);
N = 0;
//输入下一组数
N = Convert.ToInt32(Console.ReadLine());
}
}
}
}
发表于 2017-03-15 15:22:02
回复(0)
// n比相邻的都大 d[n] = max(d[n-1],d[n+1])+1 递推注意边界
// n小于其中一个 d[n] = d[max_index]+1
// n最小 d[n]=1
#include <vector>
#include <iostream>
using namespace std;
int dp(int n, vector<int> &cj, vector<int> &jj)
{
if(jj[n]>=0)return jj[n];
if(n==0)
{
if(cj[0]>cj[1])return dp(1,cj,jj)+1;
else return 1;
}
else if(n == cj.size()-1)
{
if(cj[n]>cj[n-1]) return dp(n-1,cj,jj)+1;
else return 1;
}
else
{
int left=n-1;
int right=n+1;
if(cj[n]<=cj[left] && cj[n]<=cj[right])return 1;
else if(cj[n]<=cj[left] && cj[n]>jj[right]) return dp(right,cj,jj)+1;
else if(cj[n]>cj[left] && cj[n]<=cj[right]) return dp(left,cj,jj)+1;
else return max(dp(left,cj,jj),dp(right,cj,jj))+1;
}
}
int main()
{
int n;
while(cin>>n)
{
vector<int> vc(n,0);
for(int i=0;i<n;i++)
cin>> vc[i];
vector<int> jj(n,-1);
int sum=0;
for(int i=0;i<n;i++)
sum+=dp(i,vc,jj);
cout<<sum<<endl;
}
return 0;
}
编辑于 2016-08-22 20:56:17
回复(0)
首先这道题我并没有用排序，我就是一点点寻找规律。
最开始我最直接的思路是：
第一个奖金为1，以后每次都跟左边比，如果成绩比左边大，奖金就比左边大1，否则奖金为1。题目给的例子正好能过，但是显然我忽略了连续降序的case。
比如A数组：
5,4,3,2,1
，此时第一个奖金不能为1，不然后边没法发奖金了，因为至少要发1，但是此时后面发1，就会不满意。因此正确的思路应该修正为，寻找降序序列的最低点，此时最低点是A[4]，它才是1。
而从A[3]到A[0]应该是2,3,4,5，只要注意这一点，算法就简单了。
给出java代码：
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner ins = new Scanner(System.in);
int[] z = null;
boolean b = false;
int i = 0;
while(ins.hasNextInt()){
int temp = ins.nextInt();
if(!b){
z = new int[temp];
b = true;
continue;
}
z[i++] = temp;
if(i == z.length){
int bonusMoney = caculateBonus(z);
System.out.println(bonusMoney);
b = false;
i = 0;
}
}
}
public static int caculateBonus(int[] array){
int bonus = 1;//奖金总和
int left = 1;//左边的奖金，暂且为1，后面会做补偿
int length = array.length;
for (int i = 1; i < length; ++i) {
if (array[i] > array[i - 1]) {
left++;//升序直接+1
} else if (array[i] == array[i - 1]) {
left = 1;
}
//当遇到降序时，要特殊处理，寻找降序的最低点，最低点为1，然后从最低点倒过来依次+1
else if( array[i] < array[i - 1]){
int start = i-1 ;// 记录起点
while (i < length && array[i] < array[i - 1]) {// 寻找终点
i++;
}
//回退一步，因为最后一步多加了一次
i--;
// 此时终点是i，奖金是1，从终点返回起点依次+1
int temp = 1;
for (int j = i; j > start; --j) {
bonus += temp;
temp++;
}
// 当temp比起点大时，起点位置的奖金理应是temp(此前是left)，因此我们需要加上补偿值
if (temp > left) {
bonus += (temp - left);
}
left = 1;//别忘记重新设置左边奖金为1
continue;
}
bonus += left;
}
return bonus;
}
}
发表于 2016-08-20 17:01:38
回复(1)
#include<iostream>
#include <math.h>
using namespace std;
int main()
{int a;
while(cin>>a)
{int *b=new int[a];
int *c=new int[a]();
for(int i=0;i<a;i++)
{cin>>b[i];
c[i]=1;}
for(int i=1;i<a;i++)
{
if(b[i]>b[i-1])
c[i]=c[i-1]+1;
else if (b[i]==b[i-1])
{}
else{
bool is=1;
for (int j=i-1;j>=0;j--)
{
if(is)
{
if(b[j]>b[j+1]&&c[j]<=c[j+1])
is=1;
else is=0;
}
if(is)
{
c[j]=c[j+1]+1;
}}} }
int bn=0;
for(int i=0;i<a;i++)
bn+=c[i];
cout<<bn<<endl;
}
}
最简洁的，没有之一
发表于 2016-08-17 20:22:54
回复(1)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int N;
while(cin>>N)
{
vector<int>arr(N);
for(int i=0;i<N;i++)
cin>>arr[i];
vector<int>dp(N,1);
//正向都满足条件的情况下，但是忽略了46 23 13这样的连续降的情况，所以需要反向再递推一次
dp[0]=1;
for(int i=1;i<N;i++)
{
if(arr[i]>arr[i-1])
dp[i]=dp[i-1]+1;
else if(arr[i]==arr[i-1])dp[i]=dp[i-1];
}
//反向
for(int i=N-2;i>=0;i--)
{
if(arr[i]>arr[i+1])
dp[i]=max(dp[i],dp[i+1]+1);
}
int res=0;
for(int i=0;i<N;i++)
res+=dp[i];
cout<<res<<endl;
}
return 0;
}
发表于 2016-03-21 22:34:14
回复(0)
<?php
function init()
{
$ret = array();
while ($record = trim(fgets(STDIN)))
{
$path = explode(" ", $record)[0];
$pathArray = explode("\\", $path);
$fileName = end($pathArray);
$line = intval(explode(" ", $record)[1]);
$key = $fileName." ".$line;
if ( in_array($key, array_keys($ret)) )
{
$ret[$key] = $ret[$key] + 1;
}
else
{
$ret[$key] = 1;
}
}
return $ret;
}
//排序并返回前n条记录
function stableSort( $array, $n )
{
$values = array_values( $array );
array_multisort( $values, SORT_DESC, array_keys($values), SORT_ASC, $array);
if ( sizeof($array) <= $n)
{
return $array;
}
else
{
return array_slice($array,0, $n);
}
}
//修正key
function format( $array )
{
$ret = array();
foreach ($array as $k => $v)
{
$fileName = explode(" ", $k)[0];
if ( strlen($fileName) > 16 )
{
$fileName = substr($fileName,strlen($fileName) - 16, 16);
}
$key = $fileName." ".explode(" ", $k)[1];
$ret[ $key ] = $v;
}
return $ret;
}
function myPrint( $ret )
{
foreach ($ret as $k=>$v)
{
print $k." ".$v."\n";
}
}
function main()
{
$array = init();
$ret = stableSort( $array, 8 );
$ret = format( $ret );
myPrint($ret);
}
main();
发表于 2018-10-17 10:14:17
回复(0)
while 1: try: N=int(input()) score=[int(input()) for i in range(N)] reverse=score[::-1]#分数反序排列 bonus1=[1 for i in range(N)]#初始值均为1 bonus2=[1 for i in range(N)] ans=[] for i in range(1,N):#后一个数大于前一个数，则+1 if score[i]>score[i-1]: bonus1[i]=bonus1[i-1]+1 if reverse[i]>reverse[i-1]: bonus2[i]=bonus2[i-1]+1 bonus2=bonus2[::-1]#反序 for i in range(N):#取两次排序中的较大值 ans.append(max(bonus1[i],bonus2[i])) print(sum(ans)) except: break
发表于 2018-08-30 14:33:16
回复(0)
import sys
if __name__ == "__main__":
grade = []
for i in sys.stdin:
grade.append(int(i.strip('\n')))
grade_re = grade.copy()
grade_re.reverse()
re1 = []
re2 = []
for i in range(1,grade[0]+1):
if i == 1:
re1.append(1)
continue
if grade[i-1] < grade[i]:
re1.append(re1[i-2]+1)
elif grade[i-1] == grade[i]:
re1.append(re1[i-2])
else:
re1.append(1)
for i in range(0,len(grade_re)-1):
if i == 0:
re2.append(1)
continue
if grade_re[i-1] < grade_re[i]:
re2.append(re2[i-1]+1)
elif grade_re[i-1] == grade_re[i]:
re2.append(re2[i-1])
else:
re2.append(1)
re2.reverse()
res = [max(a,b) for a,b in zip(re1,re2)]
print(sum(res))
本地测试没毛病，但是在这输出为空，不知道为啥。。。
发表于 2018-08-22 18:22:19
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-15 16:16:48 -
2022-09-14 16:18:39 -
2022-09-13 11:09:56
-
2022-09-11 21:08:55
-
2022-09-06 21:50:21
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
对于给定的一堆成绩，从开始往后，第一个初始化为 1W ，依次向后初始化 i +1 的 money 值，
当 i 对应的分数比 i+1 的分数小时， i+1 应该拿到更多的前，所以有 money[i+1]=money[i]+1;
当 i 对应的分数跟 i+1 相等时，反正也看不到，将 money[i+1] 设为 1 ；
当 i 对应的分数比 i +1 大时： money[i+1] 应该是此时较小的，将其设为 1 ，但是可能后面的跟他相同或比他小，因此要将后面分数递增的那些 money 跟新一下，此处采用一个 for 循环，循环从 k=i+1 开始，当 score[k-1]>score[k]&&money[k]+1>money[k-1] 时才 -- ，注意与后面的条件，是为了判断 money 值可能的断崖式下降（因为起始 money[i+1] 设为 1 了，可能比 money[i] 小很多）。满足条件将其值加 1.