钠 GZY整理贪心
2024-09-02 14:58:59
CF140C New Year Snowmen
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define mk make_pair
#define fi first
#define se second
const int maxN = 1e5 + 7;
inline int gi() {
int x = 0,f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
int cnt[maxN];
int a[maxN];
priority_queue<PII> q;
struct Ans {
int x,y,z;
}b[maxN];
int n;
void Read() {
n = gi();
rep(i , 1, n) a[i] = gi();
return;
}
void Pre() {
sort(a + 1,a + n + 1);
rep(i , 1, n) {
int p = lower_bound(a + 1,a + n + 1,a[i]) - a;
cnt[p] ++;
}
for(int i = 1;i <= n;++ i) {
if(cnt[i]) q.push(mk(cnt[i] , i));
}
}
void Solve() {
int k = 0;
while(q.size() >= 3) {
int x = q.top().se;q.pop();
int y = q.top().se;q.pop();
int z = q.top().se;q.pop();
b[++ k] = (Ans) {a[x] , a[y], a[z]};
if(b[k].z > b[k].y) swap(b[k].z , b[k].y);
if(b[k].y > b[k].x) swap(b[k].x , b[k].y);
if(b[k].z > b[k].y) swap(b[k].z , b[k].y);
cnt[x] --;if(cnt[x]) q.push(mk(cnt[x] , x));
cnt[y] --;if(cnt[y]) q.push(mk(cnt[y] , y));
cnt[z] --;if(cnt[z]) q.push(mk(cnt[z] , z));
}
printf("%d\n",k);
rep(i , 1, k) {
printf("%d %d %d\n",b[i].x,b[i].y,b[i].z);
}
}
int main() {
Read();
Pre();
Solve();
return 0;
}
CF161B Discounts
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define dbug(x) cout << "DEbug: " << x << '\n';
inline int gi() {
int x = 0 ,f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
int n, k;
const int maxN = 1e3 + 7;
struct Node {
int id, c;
}a[maxN];
int t[maxN];
bool cmp(Node a, Node b) {
return a.c > b.c;
}
bool vis[maxN];
int ans[maxN];
void Solve() {
double ans1 = 0;
int n = gi(), k = gi();
for(int i = 1;i <= n;++ i) {
a[i].id = i;
a[i].c = gi();
ans1 += a[i].c;
t[i] = gi();
}
sort(a + 1, a + n + 1,cmp);
int num = 0;
for(int i = 1;i <= n;++ i) {
if(num < k - 1 && t[a[i].id] == 1) {
vis[i] = true;
ans[++ num] = a[i].id;
ans1 -= 1.0 * a[i].c / 2;
}
}
bool flag = false;
int minn = 0x7fffffff;
for(int i = 1;i <= n;++ i) {
if(!vis[i]) {
if(t[a[i].id]== 1) {
flag = true;
minn = min(minn ,a[i].c);
}
}
}
int tot = num;
for(int i = 1;i <= n;++ i) {
if(!vis[i]) {
if(tot == k - 1) break;
tot ++;
ans[tot] = a[i].id;
vis[i] = true;
}
}
if(flag) ans1 -= 1.0 * minn / 2;
cout << ans1 << '\n';
for(int i = 1;i < k;++ i) {
printf("1 %d\n",ans[i]);
}
int cnt = 0;
for(int i = 1;i <= n;++ i) {
if(!vis[i]) cnt ++;
}
printf("%d ",cnt);
for(int i = 1;i <= n;++ i) {
if(!vis[i]) {
printf("%d ",a[i].id);
}
}
}
int main() {
Solve();
return 0;
}
P1842 奶牛玩杂技
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define int long long
const int inf = 0x7fffffff;
inline int gi() {
int x = 0,f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 100000 + 7;
struct Node {
int w, s;
}a[maxN];
bool cmp(Node a , Node b) {return a.s + a.w > b.s + b.w;}
signed main() {
int n = gi();
rep(i , 1, n) {
a[i].w = gi();
a[i].s = gi();
}
sort(a + 1 , a + n + 1, cmp);
int ans = -inf;
int sum = 0;
sep(i , n, 1) {
ans = max(ans , sum - a[i].s);
sum += a[i].w;
}
printf("%lld",ans);
return 0;
}
最新文章
- ImageLoader配合ImageSwitcher的使用
- 更新centos curl
- Codeforces Round #282 Div.1 B Obsessive String --DP
- js判断访问来源
- SPOJ #442 Searching the Graph
- Memcached使用
- Computer Vision的尴尬---by林达华
- http server v0.1_http_server.c
- Simple screenshot that explains the singleton invocation.
- 【转】 iOS开发UI篇—控制器的View的创建
- 无锁atomicInteger
- python解决上楼梯问题
- BPM与OA区别
- 细说Django的中间件
- ssm 连接两个数据库
- Netty 源码剖析之 unSafe.read 方法
- 【BZOJ1297】[SCOI2009]迷路（矩阵快速幂）
- javaweb项目运行时生成的Servers项目作用
- iterm2 学习笔记
- VSCode中C/C++库文件的配置