nyoj847 S + T（贪心）

nyoj847 S + T（贪心）

题目847​​题目信息​​​​运行结果​​​​本题排行​​​​讨论区​​

S + T

1000 ms  |  内存限制： 65535

2

给你一个长度为n的整数序列A1，A2，……,An,找出两个整数Ai和Aj(i

输入第一行为数据组数T（T<=100）。每组数据的第一行为整数的个数n(2<=n<=100000)；一下n行，每行为一个绝对值不超过150000的正整数。(所有的数据都不超过2^64 - 1) 输出 对于每组数据，输出Ai –Aj的最大值、i值和j值。（如果有多个最大值，则输出先出现的最大值和i,j值） 样例输入

235 2 162 3 6 2 1 -1

样例输出

4 1 37 3 6

提示 如果你认为数据太大，则本OJ推荐使用long long

​

刚开始用的结构体优先队列，结果发现wa了几次才发现，i>j...也就是说前面的数减去后面数的最大值。

想想还是把wa的贴出来吧。AC贪心策略是,先把数据用数组保存起来，然后for循环从0-n筛选最大值，保存起来，从n-0筛选最小值，保存起来。

最后再用一个for循环寻找差的最大值。具体看下面ac代码。

wa:

#include #include using namespace std;struct node{ long long t,num; bool operator<(const node &a)const { if(nums;int main(){ long long ncase,mark1,mark2,sum,n,mark; node x,y1,y2,temp; scanf("%lld",&ncase); while(ncase--) { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&x.num); x.t=i; s.push(x); } y1=s.top(); while(s.size()>1) { temp=s.top(); if(temp.num!=y1.num) break; else mark=temp.t,s.pop(); } while(s.size()>1) s.pop(); y2=s.top(),s.pop(); printf("%lld",y1.num-y2.num); if(y1.num!=y2.num) printf(" %lld %lld\n",mark,y2.t); else printf(" 1 2\n"); } return 0;}

ac:

#include #include #define N 100005long long num[N];struct node{ long long max,t1,min,t2; }c[N];int main(){ long long t,n,temp,mark1,mark2; scanf("%lld",&t); while(t--) { memset(num,0,sizeof(num)); memset(&c,0,sizeof(&c)); scanf("%lld",&n); temp=-150005; for(int i=0;i=0;i--) { if(num[i]<=temp) temp=num[i],mark2=i+1; c[i].min=temp; c[i].t2=mark2; } temp=-150005*2; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。