如何打印总和等于最大总和的数字 [英] How do I print the numbers whose sum is equal to the maximum sum
问题描述
在XYZ社会中，邻居互相讨厌他们的态度。为迎接新的一年，社会组织了各种活动。门票被提供给每个房子，上面写着整数。有些人获得正整数的门票，有些人得到带负整数的门票。晚上，人们不得不把门票带到俱乐部会所，那里有资格的人会得到令人兴奋的礼物。赢得礼物的资格取决于可以从门票号码形成的最大金额，记住邻居互相仇恨。由于邻居彼此讨厌，两者不能在最大总和列表中。
社会主席辛格先生是个聪明人，知道邻居在社会中不喜欢彼此。而且，他不希望在人们面前变坏。因此，他提出了一个设计程序的想法，该程序将提供形成最大总和的整数列表，因此列表中的所有成员都将获得礼物。这个想法唯一的问题是他不懂编程所以他要求你提供正确的整数列表。人们可能很讨厌，但很聪明，如果你提供的清单没有形成最高金额，他们会打架。
注：个人票上写的整数可能是也可能不是唯一的。如果有两个具有相等最大总和的列表，则将考虑具有第一个更大元素的列表。为了更好地理解，请查看示例测试用例中的测试用例4的说明。整数0的门票不算是赢得礼物。
输入格式
第一行输入包括多个测试用例，T。
每个测试用例的第一行包括社会中的房屋数量（门票分发），N。
每个测试用例的第二行包含N个空格分隔的票据，上面写着整数。
约束
1< = T< = 10
1< = N< = 10000
-1000< = Integer_on_Ticket< = 1000
输出格式
对于每个测试用例，将票号打印在一行中形成最大值以与Sample Test Case类似的格式求和。
我尝试过：
In the XYZ society, the neighbours hate each other for their attitude. Various activities are organized in the society for Welcoming the New Year. The tickets were provided to each house with an integer written on it. Some got tickets with positive integers and some got tickets with negative integers. In the evening, people had to carry their tickets to the club house where the eligible ones will get the exciting gifts. The eligibility of winning the gift depends on the maximum sum which can be formed from the tickets numbers keeping in mind that neighbours hate each other. Since the neighbours hate each other, the two cannot be together in the list of maximum sum.
The President of the society, Mr. Singh, is a wise man and know that neighbours in society don't like each other. Also, he don't wish to become bad in front of people. So, he came up with an idea to design a program which will provide the list of integers forming maximum sum and thus all the members of the list will be given the gifts. The only problem with this idea is that he don't know programming so he is asking you to provide the correct list of integers. The people may be annoying but are smart and will fight if the list provided by you doesn't form the maximum sum.
Note: The integer written on ticket of individuals may or may not be unique. In case, when there are two list with equal maximum sum, the list with first greater element would be considered. For better understanding, look at the explanation of Test case 4 in Sample Test Case. The tickets with integer 0 are not considered for winning the gifts.
Input Format
The first line of input consist of number of test cases, T.
The first line of each test case consist of the number of houses (tickets distributed) in society, N.
The second line of each test case consist of N space separated tickets with integer written on them.
Constraints
1<= T <=10
1<= N <=10000
-1000<= Integer_on_Ticket <=1000
Output Format
For each test case, print the ticket numbers in a single line forming the maximum sum in the format similar to Sample Test Case.
What I have tried:
#include<iostream>
using namespace std;
void maxsum(int a[], int n);
int maxi(int a, int b);
int main()
{
int t,n,i,j;
cin>>t;
while(t--)
{
cin>>n;
int a[n];
for(i=0; i<n; i++)
cin>>a[i];
maxsum(a,n);
}
return 0;
}
void maxsum(int a[], int n)
{
int m[n],max=0,i,x[n],c=0;
for(i=0; i<n; i++)
x[i]=0;
if(a[0]>0)
m[0]=a[0];
else
m[0]=0;
m[1]= maxi(a[1],a[0]);
for(i=2; i<n; i++)
{
m[i]= maxi(m[i-1], m[i-2]+a[i]);
max=m[i];
if(max == m[i-1])
{
x[c]=i-1;
c++;
}
else
{
x[c++]=i-2;
x[c++]=i;
}
}
//for(i=0; i<n; i++)
//{
// if(max<m[i])
// max=m[i];
//}
//return max;
for(int j=c; j>0; j--)
{
if(x[j]!=0)
cout<<a[x[j]];
}
}
int maxi(int a, int b)
{
return (a>b?a:b);
}
推荐答案
如何打印总和等于最大总和的数字
How do I print the numbers whose sum is equal to the maximum sum
问题是挑战网站的典型问题，根据定义，这些挑战很复杂。目标始终是创建一个解决问题的特定算法。
这是你给你的一个任务，目的是知道你是否可以解决它。
显然，你失败了。
不幸的是，为你解决这个问题永远无法帮助你解决其他问题。你的失败只是说你需要学习算法和练习。
The problem is typical from a challenges sites, by definition, those challenges are complicated. The goal is always to create a specific algorithm that solve the problem.
This is an assignment given to you by you, the whole purpose is to know if you can solve it or not.
And obviously, you fail.
Unfortunately, solving the problem for you will never help your skills to solve other problems. Your fail just say that you need to study algorithms and practice.
<pre>//sum of maximum neighburs
#include<iostream>
using namespace std;
void ins_Array(int Integer_on_Ticket[],int n)
{
for(int i=0;i<n;i++)
{
cin>>Integer_on_Ticket[i];
while(Integer_on_Ticket[i]<(-1000) || Integer_on_Ticket[i]>1000)
{
cout<<"enter again";
cin>>Integer_on_Ticket[i];
}
}
}
int check(int Integer_on_Ticket[],int s[],int n)
{
int m,k=0;
for(int i=0;i<(n-2);i++)
{
for(int j=(i+2);j<n;j++)
{
s[k]=Integer_on_Ticket[i]+Integer_on_Ticket[j];
if(s[k]<Integer_on_Ticket[i])
{
s[k]=Integer_on_Ticket[i];
}
k++;
}
}
return k;
}
int sum(int Integer_on_Ticket[],int s[],int n,int k)
{
int ma;
ma=s[0];
for(int i=0;i<k;i++)
{
if(ma<s[i])
{
ma=s[i];
}
}
return ma;
}
int maxv(int Integer_on_Ticket[],int s[],int ma,int n,int k)
{
int ans,f=0,p=0,r,t;
for(int i=0;i<(n-2);i++)
{
for(int j=(i+2);j<n;j++)
{
ans=Integer_on_Ticket[i]+Integer_on_Ticket[j];
if(ans==ma)
{
if(p==0)
{
//cout<<Integer_on_Ticket[j]<<Integer_on_Ticket[i]<<endl;
r=i;
t=j;
f=1;
p=1;
}
else if(p==1)
{
if(Integer_on_Ticket[r]<Integer_on_Ticket[i])
{
r=i;
t=j;
}
}
}
}
}
if(f==1)
{
cout<<Integer_on_Ticket[t]<<Integer_on_Ticket[r]<<endl;
}
return f;
}
int main()
{
int n,Integer_on_Ticket[200],s[200],k,T;
cout<<"enter no of test cases";
cin>>T;
while(T--)
{
cout<<"enter n";
cin>>n;
while(n<1 || n>1000)
{
cout<<"enter n";
cin>>n;
}
ins_Array(Integer_on_Ticket,n);
if(n==1)
{
cout<<Integer_on_Ticket[0];
}
else if(n==2)
{
cout<<"As neighbours hate each other";
}
else
{
k=check(Integer_on_Ticket,s,n);
int ma=sum(Integer_on_Ticket,s,n,k);
int j=maxv(Integer_on_Ticket,s,ma,n,k);
if(j==0)
{
cout<<ma;
}
}
}
return 0;
}
static int maxSubArraySum(int[] a, out List<int> res)
{
int size = a.Length;
int max_so_far = 0, max_ending_here = 0;
List<int> elements = new List<int>();
for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (a[i] > 0)
elements.Add(a[i]);
if (max_ending_here < 0)
max_ending_here = 0;
/* Do not compare for all elements. Compare only when max_ending_here > 0 */
else if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
res = elements;
return max_so_far;
}
public static void calculate()
{
try
{
int T = Convert.ToInt32(Console.ReadLine());
if (T < 1 || T > 10) return;
List<int> tickets = new List<int>();
List<string> res = new List<string>();
for (int loop = 0; loop < T; loop++)
{
int count = Convert.ToInt32(Console.ReadLine());
if (count < 1 || count > 10000) continue;
tickets = Console.ReadLine().Split(' ').ToList().Where(x => !string.IsNullOrEmpty(x)).Select(x => Convert.ToInt32(x)).ToList();
if (tickets.Any(x => x < -1000 || x > 1000)) continue;
var evens = tickets.Where((s, i) => i % 2 == 0).ToArray();
var odds = tickets.Where((s, i) => i % 2 != 0).ToArray();
List<int> resEven = new List<int>();
List<int> resodd = new List<int>();
var resEvenSum = maxSubArraySum(evens, out resEven);
var resOddSum = maxSubArraySum(odds, out resodd);
var resR = "";
if (resEvenSum >= resOddSum)
{
for (int i = resEven.Count - 1; i >= 0; i--)
{
resR += resEven[i].ToString();
}
}
else if (resEvenSum < resOddSum)
{
for (int i = resodd.Count - 1; i >= 0; i--)
{
resR += resodd[i].ToString();
}
}
res.Add(resR);
}
for (int loop = 0; loop < res.Count; loop++)
{
Console.WriteLine(res[loop].ToString().ToCharArray().Reverse().ToString());
}
}
catch (Exception ex) { Console.Write(ex.Message + ex.StackTrace); }
}
这篇关于如何打印总和等于最大总和的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
