BestCoder Round #47 ($) HDU 5280 Senior\'s Array

本文主要是介绍BestCoder Round #47 ($) HDU 5280 Senior\'s Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=5280

考少年——报考杭州电子科技大学计算机学院

Senior's Array

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 244 Accepted Submission(s): 93

Problem Description

One day, Xuejiejie gets an array A . Among all non-empty intervals of A , she wants to find the most beautiful one. She defines the beauty as the sum of the interval. The beauty of the interval--- [L,R] is calculated by this formula : beauty(L,R) = A[L]+A[L+1]+……+A[R] . The most beautiful interval is the one with maximum beauty.

But as is known to all, Xuejiejie is used to pursuing perfection. She wants to get a more beautiful interval. So she asks Mini-Sun for help. Mini-Sun is a magician, but he is busy reviewing calculus. So he tells Xuejiejie that he can just help her change one value of the element of A to P . Xuejiejie plans to come to see him in tomorrow morning.

Unluckily, Xuejiejie oversleeps. Now up to you to help her make the decision which one should be changed(You must change one element).

Input

In the first line there is an integer T , indicates the number of test cases.

In each case, the first line contains two integers n and P . n means the number of elements of the array. P means the value Mini-Sun can change to.

The next line contains the original array.

1≤n≤1000 , ?109≤A[i],P≤109 。

Output

For each test case, output one integer which means the most beautiful interval's beauty after your change.

Sample Input

Sample Output

8
2

Source

BestCoder Round #47 ($)

Recommend

hujie | We have carefully selected several similar problems for you: 5283 5282 5279 5278 5277

这个题目以前做过类似的。主要是求区间最大和。

求区间最大和的最好算法是O(n)dp的做法再枚举每个改变的数总时间复杂度是O(n^2)

比赛的时候初始化ans为0了被人hack了失去了怒上蓝名的机会，，。太弱了。

/* ***********************************************
Author        :
Created Time  :2015/7/11 21:33:13
File Name     :1.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1<<30
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;

bool cmp(int a,int b){
    return a>b;
}
ll a[maxn];
int n,p;
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int t;
	cin>>t;
	while(t--){
		cin>>n>>p;
		cle(a);
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		ll Max=-INF;
		ll last=0;
		ll ans;
		for(int j=1;j<=n;j++){
			ll tem=a[j];
			a[j]=p;
			ans=-INF;
			last=0;
			for(int i=1;i<=n;i++){
				last=max(0LL,last)+a[i];
				ans=max(ans,last);
			}
			Max=max(ans,Max);
			a[j]=tem;
		}
		printf("%I64d\n",Max);
	}
    return 0;
}

Senior's Gun

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 246 Accepted Submission(s): 100

Problem Description

Xuejiejie is a beautiful and charming sharpshooter.

She often carries n guns, and every gun has an attack power a[i] .

One day, Xuejiejie goes outside and comes across m monsters, and every monster has a defensive power b[j] .

Xuejiejie can use the gun i to kill the monster j , which satisfies b[j]≤a[i] , and then she will get a[i]?b[j] bonus .

Remember that every gun can be used to kill at most one monster, and obviously every monster can be killed at most once.

Xuejiejie wants to gain most of the bonus. It's no need for her to kill all monsters.

Input

In the first line there is an integer T , indicates the number of test cases.

In each case:

The first line contains two integers n , m .

The second line contains n integers, which means every gun's attack power.

The third line contains m integers, which mean every monster's defensive power.

1≤n,m≤100000 , ?109≤a[i],b[j]≤109 。

Output

For each test case, output one integer which means the maximum of the bonus Xuejiejie could gain.

Sample Input

Sample Output

Source

BestCoder Round #47 ($)

Recommend

hujie | We have carefully selected several similar problems for you: 5283 5282 5279 5278 5277

排序即可

/* ***********************************************
Author        :
Created Time  :2015/7/11 19:25:46
File Name     :1.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1<<30
#define maxn 100000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;

bool cmp(ll a,ll b){
    return a>b;
}
ll a[maxn],b[maxn];
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int t;
    int n,m;
    cin>>t;
    while(t--){
        scanf("%d%d",&n,&m);
        cle(a),cle(b);
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%I64d",&b[i]);
        }
        int k=min(n,m);
        sort(b+1,b+1+m);
        sort(a+1,a+1+n,cmp);
        ll ans=0;
        for(int i=1;i<=k;i++){
            ll w=a[i]-b[i];
            if(w>=0)ans+=w;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}