【Henu ACM Round#18 C】Ilya and Sticks
and 18 round ACM Henu
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
用cnt[i]记录数字i出现的次数就好。 然后i从1e6逆序到1 如果cnt[i+1]和cnt[i]>0同时成立的话。 那么得到一条边。加入到vector中。然后
如果cnt[i]>1 则cnt[i]-=2 加入i到vector中,直到cnt[i]<=1为止。
注意这两个判断的先后顺序。
否则
5 4 4 3会被认为无解。
vector的大小如果大于等于2了。
就说明找到一个矩形。
【代码】
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6;
int n,cnt[N+10];
ll ans = 0;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
#ifdef LOCAL_DEFINE
freopen("rush.txt","r",stdin);
#endif
cin >> n;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
cnt[x]++;
}
vector<int> v;v.clear();
for (int i = N;i >= 1;i--){
if (cnt[i+1]>0 && cnt[i]>0){
v.push_back(i);
if ((int)v.size()>1) {
ans+=1LL*v[0]*v[1];
v.clear();
}
cnt[i+1]--;cnt[i]--;
}
while (cnt[i]>1){
cnt[i]-=2;
v.push_back(i);
if ((int)v.size()>1) {
ans+=1LL*v[0]*v[1];
v.clear();
}
}
}
cout<<ans<<endl;
return 0;
}
相关文章
- 学习日志之synthesis and optimization(4)——banding and sharing
- MIT_6.s081_Lab8:Xv6 and Lock
- 布隆过滤器:Optimizing Bloom Filter: Challenges, Solutions, and Comparisons
- ORA-15258: user group entry number must be between string and string, inclusive ORACLE 报错 故障修复 远程处理
- The valid characters are defined in RFC 7230 and RFC 3986详解编程语言
- 条件MySQL 子句之间`AND`操作符多条件查询(mysql多个and)
- Oracle DBMS: Empowering Businesses with Reliability and Performance(dbmsoracle)
- Optimizing Performance with MySQL and Tracking Data Quantity(mysqland数量)
- Unlock the Power of Oracle: Tips and Tricks for Successful Sharing(分享oracle)
- 10 Ways to Effectively Manage and Cleanup .bak Files in Linux(linux.bak)
- Exploring Oracle: Insights and Tips from the Experts(oracle分享)
- Exploring the Benefits of TC and Linux Together: Boosting Network Performance and Security.(tclinux)
- Oracle中使用除了And的其他查询关键字(oracle中除了and)
- Tutorials for Software Developers and Technopreneurs