题目1 : 工作城市分配
描述
H公司在北京和上海两个城市各有一间办公室。该公司最近新招募了2N名员工，小Hi负责把这2N名员工分配到北京和上海各N名。
于是小Hi调查了新员工对于北京和上海的意愿，我们用Bi和Si表示。Bi代表如果分配第i名员工去北京，他的满意指数；Si代表如果分配去上海，他的满意指数。
小Hi想知道如何分配才能使2N名员工的满意指数之和最高。
输入
第一行包含一个整数N。
以下2N行每行包含两个整数Bi和Si。
1 ≤ N ≤ 1000
0 ≤ Bi, Si ≤ 100000
输出
一个整数代表最高可能的满意指数之和。
- 样例输入
-
2
100 50
80 80
50 100
10 30 - 样例输出
-
310
#include <bits/stdc++.h>
using namespace std;
const int N = ;
struct Node{
int b, s;
}node[N];
bool cmp(const Node a, const Node b){
return (a.b-a.s) > (b.b-b.s);
}
int main()
{
int n;
cin>>n;
for(int i = ; i < *n; i++){
cin>>node[i].b>>node[i].s;
}
sort(node, node+*n, cmp);
int ans = ;
for(int i = ; i < *n; i++){
if(i < n)ans += node[i].b;
else ans += node[i].s;
}
cout<<ans<<endl;
return ;
}
题目2 : 工作城市分配2
描述
H公司在北京、上海和纽约三个城市各有一间办公室。该公司最近新招募了3N名员工，小Hi负责把这3N名员工分配到北京、上海和纽约各N名。
于是小Hi调查了新员工对于北京、上海和纽约的意愿，我们用Bi、Si和Ni表示。Bi代表如果分配第i名员工去北京，他的满意指数；Si代表如果分配去上海的满意指数；Ni代表如果分配去纽约的满意指数。
小Hi想知道如何分配才能使3N名员工的满意指数之和最高。
输入
第一行包含一个整数N。
以下3N行每行包含两个整数Bi、Si和Ni。
1 ≤ N ≤ 100
0 ≤ Bi, Si, Ni ≤ 100000
输出
一个整数代表最高可能的满意指数之和。
- 样例输入
-
2
100 50 100
80 80 100
50 100 100
10 30 100
80 40 30
20 70 50 - 样例输出
-
550
#include <bits/stdc++.h>
using namespace std;
const int N = ;
struct Node{
int b, s, n;
}node[N];
// dp[i][j][k] 表示前i个人，j个分配到北京，k个分配到上海，i-j-k个分配到纽约的最大满意度
int dp[][][];
int main()
{
int n;
cin>>n;
for(int i = ; i <= *n; i++){
cin>>node[i].b>>node[i].s>>node[i].n;
}
memset(dp, , sizeof(dp));
dp[][][] = node[].b;
dp[][][] = node[].s;
dp[][][] = node[].n;
for(int i = ; i <= *n; i++){
for(int j = ; j <= n; j++){
for(int k = ; k <= n; k++){
if(i-j-k>n || i-j-k<)continue;
if(j+<=n)dp[i+][j+][k] = max(dp[i+][j+][k], dp[i][j][k]+node[i+].b);
if(k+<=n)dp[i+][j][k+] = max(dp[i+][j][k+], dp[i][j][k]+node[i+].s);
if(i-j-k+<=n)dp[i+][j][k] = max(dp[i+][j][k], dp[i][j][k]+node[i+].n);
}
}
}
cout<<dp[*n][n][n]<<endl;
return ;
}
题目3 : 顺子组合
描述
你有一个包含N个整数的数组：A1, A2, ... AN。我们将3个或3个以上数值连续的整数序列称作顺子，例如[1, 2, 3]、[5, 6, 7, 8]和[10, 11, 12, 13, 14, 15, 16]都是顺子。
请你判断A数组是否能拆分成若干个顺子的组合。要求每个整数Ai恰好只属于其中一个顺子。
输入
第一行包含一个整数T代表测试数据的组数。
每组数据第一行包含一个整数N。
每组数据第二行包含N个整数A1, A2, ... AN。
1 ≤ T ≤ 10
1 ≤ N ≤ 10000
0 ≤ Ai ≤ 100000
输出
对于每组数据输出YES或者NO代表是否能拆分成顺子组合。
- 样例输入
-
2
7
4 1 3 2 5 4 6
8
4 1 3 2 5 4 6 6 - 样例输出
-
YES
NO
#include <bits/stdc++.h>
using namespace std;
int book[];
bool check(int n){
for(int i = ; i <= n; i++){
while(book[i]){
int len = ;
for(int j = i; j <= n; j++){
len++;
book[j]--;
if(book[j+] <= book[j])break;
}
if(len < )return false;
}
}
return true;
}
int main()
{
int T, n, a;
cin>>T;
while(T--){
cin>>n;
int len = -;
memset(book, , sizeof(book));
for(int i = ; i < n; i++){
cin>>a;
book[a]++;
len = max(len, a);
}
if(check(len))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return ;
}
题目4 : 栈的加强版
描述
请你实现一个加强版的栈，支持以下操作：
push x: 向栈顶加入一个整数x
pop: 从栈顶弹出一个整数，并且输出该整数
inc k x: 将处于栈底的前k个整数加x。
输入
第一行包含一个整数N，代表操作的数量。
以下N行每行一条操作。
1 ≤ N ≤ 200000, 0 ≤ x ≤ 100000, 1 ≤ k ≤ 当前栈的大小
输出
对于每一个pop操作，输出弹出的整数数值。
- 样例输入
-
6
push 1
inc 1 2
push 2
inc 2 2
pop
pop - 样例输出
-
4
5
#include <bits/stdc++.h> using namespace std; int sk[], top, fg[]; int main()
{
int n, a, b;
cin>>n;
string op;
top = -;
memset(fg, , sizeof(fg));
while(n--){
cin>>op;
if(op=="push"){
cin>>a;
sk[++top] = a;
}else if(op=="inc"){
cin>>a>>b;
fg[a-] += b;
}else if(op=="pop"){
cout<<sk[top]+fg[top]<<endl;
fg[top-] += fg[top];
fg[top] = ;
top--;
}
} return ;
}