A. Holidays
题意：一个星球 五天工作，两天休息。给你一个1e6的数字n，问你最少和最多休息几天。
思路：我居然写成模拟题QAQ。
#include<bits/stdc++.h>
using namespace std; //#define int long long signed main(){
int n;
cin>>n;
if(n%==){
int x=n/;x*=;
cout<<x<<" "<<x;
return ;
}
int ans1=;
int ans2=;
int i=;
int temp=n;
while(){
if(temp<=)
break;
if(i%)
temp-=;
else{
ans1+=min(temp,);temp-=min(temp,);
}
i++;
if(temp<=)
break;
}
i=;
temp=n;
while(){
if(temp<=)
break;
if(i%==)
temp-=;
else
ans2+=min(temp,),temp-=min(temp,);
i++;
if(temp<=)
break;
}
cout<<ans1<<" "<<ans2;
return ;
}
/*
6
1 2
7
2 2
8
2 3
9
2 4 */
B. Game of Robots
题意：第一个机器人报自己的编号；第二个报前一个机器人和自己的编号；第三个机器人报前两个机器人和自己的编号。以此类推。
每个机器人一个编号。问k个报什么。
思路：简化M的值。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define N 1500050
int arr[N]; signed main(){
int n,m;
cin>>n>>m; for(int i=;i<=n;i++){
cin>>arr[i]; if(m<=i){
continue;
}else{
m-=i;
}
}
cout<<arr[m];
return ;
}
C. Cinema
题意：有n个人，每个人只会一种语言（不同编号表不同语言）。
现在有m部电影，每部电影的声音是a[i],字幕是b[i]。（a[i]输入完输入b[i]）
如果听得懂声音，他会非常满意，如果字幕他能看懂的话他会比较满意，否则它很不满意。
现在问看哪部电影会使得n个人满意最高（如果两部电影使n个人非常满意的人数相同时，选比较满意的最多的）。
思路：看了一些大佬的博客，都是用离散化。可是菜菜的我不会离散化QAQ。结果用个哈希MAP。居然水过。unordered_map<int,int> mp是个好东西。。。。。。。。。。。
#include<bits/stdc++.h> using namespace std;
#define int long long
struct str{
int x,y,id;
}st[];
unordered_map<int,int> mp;
bool cmp(str a,str b){
if(mp[a.x]!=mp[b.x]){
return mp[a.x]>mp[b.x];
}else{
return mp[a.y]>mp[b.y];
}
}
signed main(){
int n;
cin>>n;
for(int i=;i<=n;i++){
int temp;
scanf("%lld",&temp);
mp[temp]++;
}
int m;
cin>>m;
for(int i=;i<=m;i++){
scanf("%lld",&st[i].x);
st[i].id=i;
}
for(int i=;i<=m;i++){
scanf("%lld",&st[i].y);
}
sort(st+,st++m,cmp);
cout<<st[].id;
return ;
}
D1. Magic Powder
题意：做一个蛋糕需要n个原材料，现有k个魔法材料，魔法材料可以替代成任何材料，现在告诉你蛋糕每个材料需要多少，以及你现在有多少个，问你最多能够做出多少个蛋糕来。
思路：看了一下数据范围，然后开始暴力。
AC代码：
/* 10 926
5 6 8 1 2 5 1 8 4 4
351 739 998 725 953 970 906 691 707 1000
*/
#include<bits/stdc++.h> using namespace std;
#define int long long
map<int,int> mp;
int arr[];
signed main(){
int n,m;
cin>>n>>m;
int temp;
for(int i=;i<=n;i++){
scanf("%lld",&temp);
mp[i]=temp;
}
for(int i=;i<=n;i++){
scanf("%lld",&arr[i]);
}
int ans=;
while(){
int flag=;
for(int i=;i<=n;i++){
if(arr[i]>=mp[i]){
arr[i]-=mp[i];
}else{
int x=mp[i]-arr[i];
if(x<=m){
m-=x;
arr[i]+=x;
arr[i]-=mp[i];
}else{
flag=;
break;
}
}
}
if(flag){
ans++;
}else{
break;
}
}
cout<<ans; return ;
}
D2. Magic Powder
二分做法。感觉以前做过类似的题目。
#include<bits/stdc++.h> using namespace std;
#define N 190000
#define int unsigned long long
int n,k;
int arr[N];
int vis[N];
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=;i<=n;i++)
{
int temp;
scanf("%lld",&temp);
vis[i]=temp;
}
for(int i=;i<=n;i++)
{
scanf("%lld",&arr[i]);
}
int l=;
int r=;
while(l<=r){
int mid=(l+r)/;
int sum=;
for(int i=;i<=n;i++){
if(arr[i]<vis[i]*mid){
sum+=vis[i]*mid-arr[i];
}
if(sum>k){
break;
}
}
if(sum==k){
cout<<mid;
return ;
}else if(sum<k){
l=mid+;
}else{
r=mid-;
}
}
cout<<l-;
return ;
}