题解

9 条题解

  • 0
    @ 2016-11-03 19:45:29

    哈哈哈哈哈哈哈哈哈哈哈

  • 0
    @ 2016-11-03 19:45:25

    啊啊啊啊啊啊啊啊啊啊啊

  • 0
    @ 2016-10-01 19:47:33

    #include <cstdio>

    int main()
    {
    int n;
    scanf("%d",&n);
    static int A[1000000];
    long long AA=0;
    for(int i=0;i<n;i++){
    scanf("%d",A+i);
    AA+=A[i];
    }
    long long l=0,r=AA+1;
    while(l+1<r){
    long long m=(l+r)/2;
    static long long S[1000000];
    static int P[1000000];
    for(int i=0;i<n;i++){
    if(i>0){
    P[i]=P[i-1]-1;
    S[i]=S[i-1]-A[i-1];
    }
    else{
    P[i]=0;
    S[i]=0;
    }
    while(S[i]<m){
    S[i]+=A[(i+P[i])%n];
    P[i]++;
    }
    }
    bool B=0;
    for(int i=0;i<n;i++){
    if(AA-S[i]-S[(i+P[i])%n]>=m){
    B=1;
    }
    }
    if(B){
    l=m;
    }
    else{
    r=m;
    }
    }
    printf("%lld\n",l);
    return 0;
    }

  • 0
    @ 2014-10-26 19:57:22

    太简单不管了……我的口述题解应该已经够了…………

  • 0
    @ 2014-10-26 12:04:58

    应该是二分答案+贪心,在贪心的时候注意起点变化后移动后面的两个点就行了

  • 0
    @ 2014-10-26 08:34:55

    #include <cstdio>

    int main()
    {
    int n;
    scanf("%d",&n);
    static int A[1000000];
    long long AA=0;
    for(int i=0;i<n;i++){
    scanf("%d",A+i);
    AA+=A[i];
    }
    long long l=0,r=AA+1;
    while(l+1<r){
    long long m=(l+r)/2;
    static long long S[1000000];
    static int P[1000000];
    for(int i=0;i<n;i++){
    if(i>0){
    P[i]=P[i-1]-1;
    S[i]=S[i-1]-A[i-1];
    }
    else{
    P[i]=0;
    S[i]=0;
    }
    while(S[i]<m){
    S[i]+=A[(i+P[i])%n];
    P[i]++;
    }
    }
    bool B=0;
    for(int i=0;i<n;i++){
    if(AA-S[i]-S[(i+P[i])%n]>=m){
    B=1;
    }
    }
    if(B){
    l=m;
    }
    else{
    r=m;
    }
    }
    printf("%lld\n",l);
    return 0;
    }

  • 0
    @ 2014-10-26 08:34:32

    /* Template the Final Chapter Light --- Fimbulvetr version 0.1 /
    /
    In this blizzard, I will find peace. */
    # define LOCAL
    # include <cstring>
    # include <cstdio>
    # include <algorithm>
    # include <vector>
    # include <string>
    # include <set>
    # include <map>
    using namespace std;
    # define REP( i, n ) for ( int i = 1; i <= n; i ++ )
    # define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
    # define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
    # define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
    # define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
    # define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
    # define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
    # define RST( a ) memset ( a, 0, sizeof ( a ) )
    # define CLR( a, x ) memset ( a, x, sizeof ( a ) )
    # define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
    typedef long long LL;
    const int inf = 1 << 30;

    # define NS 200100
    int n;
    LL a[ NS ], sum[ NS ];

    bool Check ( LL len )
    {
    int mid = 0, nxt = 0;
    REP_0 ( st, n )
    {
    while ( mid <= st + n && sum[ mid ] - sum[ st ] < len ) mid ++;
    if ( mid <= st + n )
    {
    while ( nxt <= st + n && sum[ nxt ] - sum[ mid ] < len ) nxt ++;
    if ( nxt <= st + n && sum[ st + n ] - sum[ nxt ] >= len ) return true;
    }
    }
    return false;
    }
    int main ()
    {
    scanf ( "%d", &n );
    REP ( i, n ) scanf ( "%lld", &a[ i ] ), sum[ i ] = sum[ i - 1 ] + a[ i ];
    REP ( i, n ) sum[ i + n ] = sum[ i + n - 1 ] + a[ i ];
    LL l = 0, r = 1LL << 60;
    for ( ; l < r; )
    {
    LL mid = ( l + r + 1 ) / 2;
    if ( Check ( mid ) ) l = mid;
    else r = mid - 1;
    }
    printf ( "%lld\n", l );
    return 0;
    }

  • 0
    @ 2014-10-26 07:24:34

    二分答案+前缀和+二分查找

  • 0
    @ 2014-10-25 22:17:04

    二分查找呢

  • 1

信息

ID
1894
难度
7
分类
(无)
标签
(无)
递交数
557
已通过
96
通过率
17%
被复制
2
上传者