Sentou
原题：Sentou
原题大意
一个水龙头，按一次开关会流T秒，再次按开关会刷新它的时间。给出n次按开关的时刻，问总共会流多少秒。
算法分析
水题，用一个数组记录两次开关的时间差，并判断前一个时刻加上水流的时间能否到达下次按开关的时刻，如果能则加上时间差，否则加上水流时间。
程序代码
#include <cstdio>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 200000+5;
typedef long long ll;
ll sen[maxn], a[maxn];
ll sum = 0;
int n;
ll t;
int main(){
scanf("%lld%lld",&n, &t);
for(int i = 0; i < n; i++)
{
scanf("%lld", &sen[i]);
}
for(int i = 1; i < n; i++)
{
a[i] = sen[i] - sen[i-1];
}
sum = 0LL;
int i = 0;
while(i < n){
if(t + sen[i] > sen[i+1]) sum+=a[i+1];
else sum+=t;
i++;
}
sum+=t;
printf("%lld\n", sum);
return 0;
}
Simple Knapsack
原题大意
0/1背包，有不超过100的物品N个，背包总容量W有10^9，会爆数组，另外重量只有四种。
算法分析
暴力枚举，时间复杂度：(N/4)^4 = 25^4 = 390625。
程序代码
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 105;
typedef long long ll;
int tot = 0;
ll a[4];
ll b[4][N];
int n ;
ll W;
vector<ll> bag[4];
set<ll> s;
bool cmp(ll a, ll b){
return a>b;
}
int main(){
scanf("%d%lld",&n,&W);
for(int i = 0; i < n; i++){
ll w,v;
int num = 0;
scanf("%lld%lld",&w, &v);
if(!s.count(w)){
s.insert(w);
num = tot;
a[tot++] = w;
}
else{
for(int j = 0; j < tot; j++)
{
if(w == a[j])
{
num = j;
break;
}
}
}
bag[num].push_back(v);
}
for(int i = 0; i < 4; i++){
sort(bag[i].begin(), bag[i].end(),cmp);
}
for(int i = 0; i < 4; i++)
{
b[i][0] = 0;
int j;
for(j = 1; j <= bag[i].size(); j++)
{
b[i][j] = bag[i][j-1]+b[i][j-1];
}
}
ll maxans = 0;
int len0 = bag[0].size();
int len1 = bag[1].size();
int len2 = bag[2].size();
int len3 = bag[3].size();
for(int i = 0; i <= len0; i++){
for(int j = 0; j <= len1; j++){
for (int k = 0; k <= len2; k++){
for(int l = 0; l <= len3; l++){
ll temp = i*a[0]+j*a[1]+k*a[2]+l*a[3];
if(temp <= W){
ll ans = b[0][i]+b[1][j]+b[2][k]+b[3][l];
if(ans > maxans) maxans = ans;
}
}
}
}
}
printf("%lld\n", maxans);
return 0;
}
Ball Coloring
原题大意
N个包，每个包里有两个球，让你将它们一红一蓝，使得(Rmax−Rmin)×(Bmax−Bmin)最小。
算法分析
令：
MIN = min(x1, x2, …, xn, y1, y2, …, yn)
MAX = max(x1, x2, …, xn, y1, y2, …, yn)
所以MIN = Rmin 或 Bmin， MAX = Rmax 或 Bmax；
考虑MIN = Rmin 和 MIN = Bmin是等价的，所以令MIN = Rmin，然后又两种情况：
- Rmin = MIN & Bmax = MAX
要取得最小值，就要是Rmax最小，Bmin最大，这样只要贪心的让每个包里的大数是蓝色的，小数是红色的。 - Rmin = MIN & Rmax = MAX
这样(Rmax−Rmin)其实已经确定，只要关注Bmax - Bmin就行了，可以先将每个包里的数值较小的球涂成蓝色的，然后从小到大排序，然后从小到大依次将蓝球与红球互相调换颜色，并且维护(Bmax−Bmin)的最小值，这样做的依据是：假设前面最小的蓝球换成红球之后Bmax不变，那么Bmin一定会变大（因为换之前红球数值大于蓝球），即使后来Bmax改变了，也只会变大，而且Bmin也一定变大，所以能得到最小值。
程序代码
//用了set里的multiset，可以使元素有序且允许重复。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = (1e5)+1;
int n;
vector<pair<ll, ll> > a;
multiset<ll> r, b;
long long ans = LLONG_MAX;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
a.resize(n);
for(int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
if(a[i].first > a[i].second)
swap(a[i].first, a[i].second);
}
sort(a.begin(), a.end());
for(auto p: a) {
r.insert(p.first);
b.insert(p.second);
}
ans = min((*r.rbegin() - *r.begin()) * (*b.rbegin() - *b.begin()), ans);
for(auto p: a) {
r.erase(r.find(p.first));
b.erase(b.find(p.second));
r.insert(p.second);
b.insert(p.first);
ans = min((*r.rbegin() - *r.begin()) * (*b.rbegin() - *b.begin()), ans);
}
cout << ans;
}
Many Moves
原题：Many Moves
原题大意
给出长度为n的数轴。你有两个指针，一开始一个在a，一个在b。q次操作，每次要求将一个指针移动到pi。移动的代价是移动前后位置的距离。最小化距离之和。
算法分析
程序代码
#include <bits/stdc++.h>
#define MAXN (1 << 18)
#define ll long long
int n, q, A, B;
int x[MAXN];
ll seg1[MAXN << 1], seg2[MAXN << 1];
ll query(ll *seg, int u, int l, int r, int ql, int qr){
if(ql <= l && r <= qr) return seg[u];
int m = l + r >> 1, ls = u << 1, rs = ls | 1;
ll ret = LLONG_MAX;
if(!(m < ql)) ret = std::min(ret, query(seg, ls, l, m, ql, qr));
if(!(qr < m + 1)) ret = std::min(ret, query(seg, rs, m + 1, r, ql, qr));
return ret;
}
void insert(ll *seg, int u, int l, int r, int pos, ll val){
if(l == r){
seg[u] = val;
return;
}
int m = l + r >> 1, ls = u << 1, rs = ls | 1;
if(pos <= m) insert(seg, ls, l, m, pos, val);
else insert(seg, rs, m + 1, r, pos, val);
seg[u] = std::min(seg[ls], seg[rs]);
}
int main(){
scanf("%d%d%d%d", &n, &q, &A, &B);
memset(seg1, 0x7f, sizeof seg1);
memset(seg2, 0x7f, sizeof seg2);
x[0] = B;
insert(seg1, 1, 1, n, A, A);
insert(seg2, 1, 1, n, A, -A);
ll delta = 0;
for(int i = 1; i <= q; ++ i){
scanf("%d", x + i);
ll tmp1 = query(seg1, 1, 1, n, x[i] + 1, n) - x[i];
ll tmp2 = query(seg2, 1, 1, n, 1, x[i]) + x[i];
tmp1 = std::min(tmp1, tmp2);
//这里可以去掉的原因是：如果原来是INF的话，加上一个数还是很大的数，下面还是会论INF处理
// ll now = query(seg1, 1, 1, n, x[i - 1], x[i - 1]) - x[i - 1] + delta;
// if(tmp1 < now){
insert(seg1, 1, 1, n, x[i - 1], tmp1 + x[i - 1] - std::abs(x[i] - x[i - 1]));
insert(seg2, 1, 1, n, x[i - 1], tmp1 - x[i - 1] - std::abs(x[i] - x[i - 1]));
// }
delta += std::abs(x[i] - x[i - 1]);
}
ll ans = LLONG_MAX;
for(int i = 1; i <= n; ++ i){
ans = std::min(ans, query(seg1, 1, 1, n, i, i) - i + delta);
}
printf("%lld\n", ans);
return 0;
}