A. Fraction
题目链接：http://codeforces.com/contest/854/problem/A
题目意思：给出一个数n，求两个数a+b=n，且a/b不可约分，如果存在多组满足条件的a和b，输出a/b最大的a和b。
题目思路：首先a+b=n，那么暴力枚举i和n-i，且gcd(i,n-i)==1，由于i越大是n-i越小，则a/b的值越大。
代码：
//Author: xiaowuga
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX INT_MAX
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=;
const long long mod=1e9+;
typedef long long LL;
typedef int II;
typedef unsigned long long ull;
#define nc cout<<"nc"<<endl
#define sp " "
int main() {
ios::sync_with_stdio(false);cin.tie();
II n;
cin>>n;
II a,b;
for(II i=;i<=n/;i++){
if(__gcd(i,n-i)==){
a=i;b=n-i;
}
}
cout<<a<<' '<<b<<endl;
return ;
}
B. Maxim Buys an Apartment
题目链接：http://codeforces.com/contest/854/problem/B
题目意思：有n个房屋排成一排，现在其中k个房屋已经住了人，但是不知道其中的哪些房屋住进了房屋，但是小明喜欢住进邻居的房屋中有人住进的的房子里。问最少有多少个房屋满足条件，最多有多少个房屋满足条件。
题目思路：首先如果首先如果n远大于k了话，那么每一个住人的房屋，周围的两个房屋都满足小明的条件，所以我们想到每三个放一个。如果k×3>n，那么答案就是n-k，否则答案就是2×k，当然还有一些特殊情况，比如n==k还有k==0的时候，需要特判一下。
代码：
/* ***********************************************
Author :xiaowuga
Created Time :2017年10月18日 星期三 13时36分58秒
File Name :Desktop/B.cpp
************************************************ */
#include <bits/stdc++.h>
typedef long long LL;
#define endl "\n"
#define inf 0x3f3f3f3f
const long long N=;
const long long mod=1e9+;
using namespace std;
int main(){
ios::sync_with_stdio(false);cin.tie();
LL n,k;
cin>>n>>k;
cout<<(k&&k<n)<<' '<<min(n-k,*k)<<endl;
return ;
}
C. Planning
题目链接：http://codeforces.com/contest/854/problem/C
题目意思：原本有n个航班，他们的起飞时间是1-n，现在机场规定在每一天的前k分钟不能有飞机起飞，那么就得有航班起飞要延误，现在给出每个航班延误一分钟所消耗的费用，问你怎么安排飞机的起飞才能使花费最少，飞机起飞时间不能比原本的要早。
题目思路：对于一个时间，用一个优先队列处理能放在当前时间的拥有每分钟最大损失的航班，这样只需要n*logn的复杂度。
题目代码：
//Author: xiaowuga
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX INT_MAX
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=;
const long long mod=1e9+;
typedef long long LL;
typedef int II;
typedef unsigned long long ull;
#define nc cout<<"nc"<<endl
#define sp " "
int main() {
ios::sync_with_stdio(false);cin.tie();
struct node{
LL c,id;
bool operator <(const node &m) const {
return c<m.c;
}
};
LL n,k;
vector<node>a;
cin>>n>>k;
a.resize(n+);
priority_queue<node>q;
for(LL i=;i<=n;i++){
cin>>a[i].c;
a[i].id=i;
}
vector<int>ans(n+);
for(LL i=;i<=k;i++) q.push(a[i]);
for(LL i=k+;i<=n+k;i++){
if(i<=n) q.push(a[i]);
auto now=q.top();
q.pop();
ans[now.id]=i;
}
LL sum=;
for(II i=;i<=n;i++){
sum+=(ans[i]-i)*a[i].c;
}
cout<<sum<<endl;
for(II i=;i<=n;i++) cout<<ans[i]<<' ';
return ;
}