hdu 5265 pog loves szh II

By | 06月09日
Advertisement

题目链接:hdu 5265

解题思路:对输入的数取模后进行排序后二分答案即可。没有注意到溢出问题,跪了三发。。。啥都不说了,代码自有分晓(nlogn)

pog loves szh II

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1330 Accepted Submission(s): 381

Problem Description

Pog and Szh are playing games.There is a sequence with n numbers, Pog will choose a number A from the sequence. Szh will choose an another number named B from the rest in the sequence. Then the score will be (A+B) mod p.They hope to get the largest score.And what is the largest score?

Input

Several groups of data (no more than 5 groups,n≥1000).

For each case:

The following line contains two integers,n(2≤n≤100000),p(1≤p≤231−1)。

The following line contains n integers ai(0≤ai≤231−1)。

Output

For each case,output an integer means the largest score.

Sample Input

4 4

1 2 3 0

4 4

0 0 2 2

Sample Output

3

2

/**************************************************************
    Problem:poj 5265 pog loves szh II
    User: youmi
    Language: C++
    Result: Accepted
    Time:343MS
    Memory:2012K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <sstream>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define rep(i,n) for(int i=0;i<n;i++)
#define lson (step<<1)
#define rson (lson+1)
#define esp 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl;

using namespace std;
typedef long long ll;

int n,mod;
const int maxn=100000+10;
int a[maxn];
ll bs(int now,int l,int r)
{
    if(l>r)
        return 0;
    ll temp=0;
    ll ans=((ll)a[now]+a[r])%mod;/**这个处理很重要,因为a[now]+a[l到r]可以>mod,而大于mod时,最大值一定是a[now]+a[cnt-1](也就是a里的最大值),然后拿这个数与不超过mod的情况时的最大值进行比较就好了**/
    while(l<=r)
    {
        int mid=(l+r)>>1;
        temp=((ll)a[now]+a[mid])%mod;
        ans=temp>ans?temp:ans;
        if(((ll)a[now]+a[mid])>=(ll)mod)
            r=mid-1;
        else
            l=mid+1;
    }
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //printf("%I64d\n",((ll)1<<31)-1);
    while(~scanf("%d%d",&n,&mod))
    {
        int val;
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            sc(val);
            val%=mod;
            a[cnt++]=val;
        }
        sort(a,a+cnt);
        /**for(int i=0;i<cnt;i++)
            printf("%d ",a[i]);
        putchar('\n');<*/
        ll ans=0;
        ll temp;
        for(int i=0;i<cnt;i++)
        {
            temp=bs(i,i+1,cnt-1);
            //printf("a[%d]->%d,temp->%d\n",i,a[i],temp);
            ans=ans>temp?ans:temp;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

Similar Posts:

  • HDU ACM 5265 pog loves szh II

    题意:求数组中两个不同元素使得两元素和%p最大. 分析: 1.序列中的数可能超过P,将所有数读入后进行模P操作. 2.将取模后的所有数从小到大排序,现在所有数都是小于P且排好序的. 3.假设任意选了两个数X和Y,则0≤X+Y≤2P-2.若X+Y<P,则答案就是X+Y,若X+Y≥P,答案是X+Y-P. 从小到大枚举第一个数,另一个匹配的数显然是从大到小的,可以用POS记录当前另一个匹配的数的位置,每次枚举时POS递减至符合条件.可以做到O(n)的时间复杂度.这题还可以使用二分等方法. #inclu

  • ACM学习历程—HDU5265 pog loves szh II(策略 &amp;amp;&amp;amp; 贪心 &amp;amp;&amp;amp; 排序)

    Description Pog and Szh are playing games.There is a sequence with $n$ numbers, Pog will choose a number A from the sequence. Szh will choose an another number named B from the rest in the sequence. Then the score will be $(A+B)$ mod $p$.They hope to

  • HDU 5266 pog loves szh III

    题意:给出一棵树,1为根节点,求一段区间内所有点的最近公共祖先. 解法:用一棵线段树维护区间LCA.LCA是dp做法.dp[i][j]表示点i的第2^j个祖先是谁,转移方程为dp[i][j] = dp[dp[i][j - 1]][j - 1],初始的dp[i][0]可以用一次dfs求得,这样可以用logn的时间求第x个祖先或查询LCA.求第x个祖先可以从二进制的角度理解,假设x是10,转化为二进制是1010,那么只要升2^3 + 2^1个深度就可以求出第x个祖先.求LCA的具体做法是,先将点a和

  • hdu 5270 ZYB loves Xor II

    题目链接 此类数论题大多按位考虑,显然暴力会超时. 不妨对(a+b)的第i位做考虑,将a,b都模2^(i+1),显然在(a+b)∈[2^i,2^(i+1))∪[3*2^i,2^(i+2))时该位为1. 所以我们只要求大于某个数的(a+b)的个数即可 值得注意的是,为了在排序时降低复杂度,可以让mod值从大到小然后归并排序,具体见代码. #include <stdio.h> #include <string.h> #include <iostream> #include

  • HDU 5265

    pog loves szh II Accepts: 97 Submissions: 834 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 问题描述 pog在与szh玩游戏,首先pog找到了一个包含n个数的序列,然后他在这n个数中挑出了一个数A,szh出于对pog的爱,在余下的n−1个数中也挑了一个数B,那么szh与pog的恩爱值为(A+B)对p取模后的余数,pog与szh当然想让恩

  • HDU 5646 DZY Loves Partition

    题目链接: hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5646 bc:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=680&pid=1002 DZY Loves Connecting Accepts: 16 Submissions: 169 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144

  • hdu 5273 Dylans loves sequence

    题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5273 Dylans loves sequence Description Dylans is given $N$ numbers $a[1]....a[N]$ And there are $Q$ questions. Each question is like this $(L,R)$ his goal is to find the "inversions" from number $L$

  • HDU 5646 DZY Loves Partition 数学 二分

    DZY Loves Partition 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5646 Description DZY loves partitioning numbers. He wants to know whether it is possible to partition n into the sum of exactly k distinct positive integers. After some thinking he f

  • HDU 5647 DZY Loves Connecting 树形dp

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5647 题解: 令dp[u][0]表示u所在的子树中所有的包含i的集合数,设u的儿子为vi,则易知dp[u][0]=(dp[v1][0]+1)*...*(dp[vk][0]+1). 令dp[u][1]表示u所在的子树中所有的包含i的集合数的大小的和,则有dp[u][1]=dp[u][1]*(dp[v][0]+1)+dp[v][1]*dp[u][0]: 其中dp[u][1]*(dp[v][0]+1)表

  • HDU 1002 A + B Problem II(模拟)

    题目链接:Click here~~ 今天无聊,把A + B Problem II用字符串做了一遍.感觉挺有成就感的,所以记录下来吧. #include <stdio.h> #include <string.h> #define M 1005 //#include <stdlib.h> //#define creat (char *)malloc(sizeof(char)) int main() { //char *a,*b,*f; //a=creat; b=creat;

Tags: