【multimap的应用】D. Array Division
2024-08-25 07:31:26
http://codeforces.com/contest/808/problem/D
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<utility>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
ll a[maxn];
ll sum[maxn];
multimap<ll,int> m;
multimap<ll,int> ::iterator it;
pair<multimap<ll,int>::iterator,multimap<ll,int>::iterator> pos;
int main()
{
int n;
scanf("%d",&n);
memset(sum,,sizeof(sum));
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
m.insert(make_pair(a[i],i));
sum[i]=sum[i-]+a[i];
}
if(sum[n]%==)
{
printf("NO\n");
return ;
}
ll half=sum[n]/;
for(int i=;i<=n;i++)
{
ll s=sum[i]-half;
if(s==)
{
printf("YES\n");
return ;
}
else if(s>)
{
pos=m.equal_range(s);
while(pos.first!=pos.second)
{
if(pos.first->second<=i)
{
printf("YES\n");
return ;
}
pos.first++;
}
}
else
{
s=-s;
pos=m.equal_range(s);
while(pos.first!=pos.second)
{
if(pos.first->second>i)
{
printf("YES\n");
return ;
}
pos.first++;
}
}
}
printf("NO\n"); return ;
}
equal_range的用法:
//定义pair 对象position; pair数据类型是 2个 multimap<string,string>::iterator 指针。
pair<multimap<string, string>::iterator, multimap<string, string>::iterator> position;
//如果键存在,函数返回2个指针,第一个指针指向键第一个匹配的元素
//第二个指针指向键最后一个匹配的元素的下一位置
position = author.equal_range(search_item);
while (position.first != position.second)
{
cout << position.first->first << " " << position.first->second << "\n";
position.first++;
}
cout << endl;
map的find函数只能找key,所以需要把a[i]作为key,但同一个数可以出现多次,所以需要用multimap,multimap内容根据key排序后,equal_range函数key出现的区间。
最新文章
- Retrofit 备注
- 使用ZeroNet搭建P2P全球网站
- LeetCode:Longest Palindromic Substring 最长回文子串
- hdu 4602 Partition(快速幂)
- (转载) mysql中,option是保留字段么?
- statspack系列6
- 在线程中进行读取并写入文件和wenjia
- 让低版本的IE浏览器 强制渲染为IE8 或者 以上 浏览器模式
- nodejs抓取网络图片转换为base64编码的图片
- 20170709_python_学习记录
- Problem B
- Pymsql
- Php导出百万数据的优化
- Python中getopt()函数的使用
- Maven 项目 启动时 解决3 字节的 UTF-8 序列的字节 3 无效
- Linux记录-使用python临时搭建web服务器
- Nginx Server 配置
- web.config 加密/解密 正确版
- bzoj 2308 小Z的袜子(莫队算法)
- Python多进程vs多线程