题目链接：Codeforces Round #433 (Div. 2）
题意：已知分子与分母的和，求分子小于分母的 最大的最简分数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int n;
int main() {
int a, b;
scanf("%d", &n);
for(int i = n/; i >= ; --i)
if(gcd(i, n-i)==) {a = i, b = n-i; break;}
printf("%d %d\n", a, b);
retur
15ms
codeforces 854 B. Maxim Buys an Apartment【水】
题意：有标号1~n的n个公寓顺序排列在一条线，已知有k个公寓不为空 但不知道是哪k个，定义一个 空的 并且旁边至少有一个 非空的公寓 为好公寓，问最少和最多有几个 好公寓。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, k;
int main() {
int a, b;
scanf("%d %d", &n, &k);
if(k >= n/+) {a = (n!=k); b = n-k;}
else {a = (k!=); b = k*;}
printf("%d %d\n", a, b);
return ;
}
15ms
codeforces 853 A. Planning【贪心+优先队列】
题意：n个航班，原本顺序出发，现在已知前k分钟没有航班能出发，每个航班均只能延迟出发时间，已知每个航班延迟一分钟需要的花费，现在要你安排出发顺序，使得总花费最小。
题解：用优先队列维护延迟时间最大值，贪心的对每个位置取队列中的最大值。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 3e5+;
int n, k;
int c[N], a[N];
priority_queue<pair<int, int> > q;
ll ans, t;
int main() {
ans = t = ;
while(!q.empty()) q.pop();
int i, j, x;
scanf("%d %d", &n, &k);
for(i = ; i <= k+n; ++i) {
if(i <= n) {
scanf("%d", &x); t += x;
q.push(make_pair(x, i));
}
if(i > k) {
a[q.top().second] = i;
t -= q.top().first; q.pop();
}
ans += t;
}
printf("%lld\n", ans);
for(i = ; i < n; ++i)
printf("%d ", a[i]);
printf("%d\n", a[n]);
return ;
}
187ms
未完待补。。。
codeforces 853 B. Jury Meeting【贪心】
题意：有n+1个城市，0号为首都，1~n每个城市有一个人，现在要安排每个人去首都，并且所有人一起待上至少k天并且返回自己的城市（航班飞行时长为一天），给出m个航班信息（每个航班都是在 0号城市 与其他城市之间往返），求满足安排的最少花费。
题解：将航班按时间排序后，贪心算所有人在第i天前出发的最小花费和第i天后返回的最小花费，最后前缀后缀扫一下。
//因为各种细节问题WA。。QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
const int N = 1e5+;
const int M = 1e6+;
const ll inf = 2e11+;
int n, m, k;
struct node {
int d, f, t, c;
bool operator < (const node &r)const {
return d < r.d;
}
}e[N];
ll a[M], b[M];
int d[N];
int main() {
int i, j, day = , u;
ll ans = inf;
CLR(a, ); CLR(b, ); CLR(d, );
scanf("%d %d %d", &n, &m, &k);
for(i = ; i <= m; ++i) {
scanf("%d%d%d%d", &e[i].d, &e[i].f, &e[i].t, &e[i].c);
day = max(day, e[i].d);
}
int num = n, tt = ;
ll mi = ;
sort(e+, e++m);
for(i = ; i <= m; ++i) {
tt = e[i].d;
if(u=e[i].f) {
if(!d[u]) {
d[u] = e[i].c; num--;
if(!num) {
for(j = ; j <= n ; ++j)a[tt] += d[j];
mi = a[tt];
}
}
else if(d[u] > e[i].c){
if(!num) {mi -= (d[u] - e[i].c); a[tt]=mi;}
d[u] = e[i].c;
}
}
}
if(num) {puts("-1"); return ;}
CLR(d, ); num = n;
for(i = m; i >= ; --i) {
tt = e[i].d;
if(u=e[i].t) {
if(!d[u]) {
d[u] = e[i].c; num--;
if(!num) {
for(j = ; j <= n ; ++j)b[tt] += d[j];
mi = b[tt];
}
}
else if(d[u] > e[i].c){
if(!num) {mi -= (d[u] - e[i].c); b[tt]=mi;}
d[u] = e[i].c;
}
}
}
if(num) {puts("-1"); return ;} for(i = ; i <= day; ++i) {
if(!a[i]) a[i] = a[i-];
else if(a[i-]) a[i] = min(a[i], a[i-]);
}
for(i = day; i >= ; --i) {
if(!b[i]) b[i] = b[i+];
else if(b[i+]) b[i] = min(b[i], b[i+]);
} //for(i = 1; i <= day; ++i) printf("%d ",a[i]);puts("");
//for(i = day; i >= 1; --i) printf("%d ",b[i]);puts(""); for(i = ; i <= day; ++i)
if(a[i] && i++k <= day && b[i++k])
ans = min(ans, a[i]+b[i++k]);
if(ans<inf) printf("%lld\n", ans);
else puts("-1");
return ;
}
93ms