AtCoder Beginner Contest 067 C - Splitting Pi
C - Splitting Pile
Time limit : 2sec / Memory limit : 256MB
Score : 300 points
Problem Statement
Snuke and Raccoon have a heap of N cards. The i-th card from the top has the integer ai written on it.
They will share these cards. First, Snuke will take some number of cards from the top of the heap, then Raccoon will take all the remaining cards. Here, both Snuke and Raccoon have to take at least one card.
Let the sum of the integers on Snuke's cards and Raccoon's cards be x and y, respectively. They would like to minimize |x−y|. Find the minimum possible value of |x−y|.
Constraints
- 2≤N≤2×105
- −109≤ai≤109
- ai is an integer.
Input
Input is given from Standard Input in the following format:
N
a1 a2 … aN
Output
Print the answer.
Sample Input 1
6
1 2 3 4 5 6
Sample Output 1
1
If Snuke takes four cards from the top, and Raccoon takes the remaining two cards, x=10, y=11, and thus |x−y|=1. This is the minimum possible value.
Sample Input 2
2
10 -10
Sample Output 2
20
Snuke can only take one card from the top, and Raccoon can only take the remaining one card. In this case, x=10, y=−10, and thus |x−y|=20.
前缀和查询
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define PI 3.141592653589793238462
#define INF 1000000000
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll x,sum[],n,ans,minn;
int main()
{
scanf("%lld",&n);
sum[]=;
for(ll i=;i<=n;i++)
{
scanf("%lld",&x);
sum[i]=sum[i-]+x;
}
ans=sum[n];
minn=abs(*sum[]-sum[n]);
for(ll i=;i<=n-;i++)
{
minn=min(minn,abs(*sum[i]-sum[n]));
}
printf("%lld\n",minn);
return ;
}
最新文章
- Online Judge(OJ)搭建(第一版)
- Design7:数据删除设计
- Busybox下mdev配置说明
- HTTP深入浅出 http请求
- 转:CentOS 7 安装Nginx
- JADE平台入门
- Unity3D中的Coroutine详解
- pfSense配置基于时间的防火墙规则
- [蓝桥杯]2013蓝桥省赛B组题目及详解
- global与nonlocal关键字
- Mac新系统常用设置
- 解决 scapy “NameError: global name &#39;wrpcap&#39; is not defined” 错误
- Linux 环境下安装Redis的步骤
- LevelDB源码分析-Version
- node 项目中 koa2 环境搭建 以及项目发布
- cactiez v11添加对mysql数据库、apache系统进行监控
- docker 安装nginx、php-fpm
- L271 操纵太空中航天器的几种方法
- Python tricks(3) -- list和dict的遍历和方法
- Codeforces Beta Round #12 (Div 2 Only)
热门文章
- Git 修改commit message
- enterprise architect (EA) 源码生成UML类图,帮助理解项目工程
- zookeeper 安装笔记 3.6.7
- Android基础笔记(十三)- 内容提供者原理和简单使用
- hdu 2191 悼念512汶川大地震遇难同胞——珍惜如今,感恩生活
- 汇编中中括号[]作用以及lea和mov指令的区别
- Java多线程理解:线程安全的集合对象
- 32.智能指针auto_ptr
- java9新特性-21-java的动态编译器
- C#篇(二)——属性的实质